#include<iostream>

#include <cstdio>

#include<algorithm>

#include <chrono>


using namespace std;


int arr[1000001];

int chk[200002];

int dp[1000001][1000001];


int main(void)

{

int n, m, i, j,sum=0;


memset(arr, 1001, sizeof(arr));

memset(chk, 0, sizeof(chk));

memset(dp, 0, sizeof(dp));


do {

cin >> n >> m;

} while (m < n);


for (i = 0; i < n; i++)

{

cin >> arr[i];

if (arr[i] > 1000 && arr[i] < -1000)

i--;

}


for (i = 0; i < m * 2; i++)

{

cin >> chk[i];

if (chk[i] > chk[i + 1])

i--;

}


for (i = 0; i < m; i++)

{

for (j = chk[2 * i] - 1; j <= chk[2 * i + 1]; j++)

{

if (dp[chk[2 * i]][chk[2 * i + 1]] !=0)

break;

dp[chk[2 * i]][chk[2 * i + 1]] += j;

}

cout << dp[chk[2 * i]][chk[2 * i + 1]] << endl;

}


return 0;

}


codeup 기억력테스트 7 dp로 풀려고 했는데,

전역변수 선언할때 dp부분 배열이 너무 크다고 하면서 선언이 안됩니다.

( 1 <= n <= 1,000,000 ) , ( 1 <= m <= 100,000 ) 

n m 개 입력 받아서 해당 배열 안의 수를 합해서 출력하는건데


6 3 3 5 2 1 4 3 2 4 1 1 1 3


이 예시에서 dp로 처리하는 다른 좋은 방법 있으면 알려주세요..