Submission #1178833


Source Code Expand

#include <bits/stdc++.h>
using namespace std;


int dp[410][410] = {}; //	dp

int main(){
	int w = 400;
	int n;
	cin >> n;
	vector<int> a(n), s(n);
	for(int i = 0 ; i < n ; i++){
		int b;
		cin >> a[i] >> b;
		s[i] = b - a[i];
	}
	for(int i = 0 ; i < n ; i++){
		multiset<int> S;
		int A = !i?0:s[i-1];
		int B = s[i];
		for(int j = 0 ; j < B ; j++)
			S.insert(dp[i][j]);

		for(int j = 0 ; j <= w ; j++){
			if( j + B <= w ){
				S.insert(dp[i][j+B]);
			}
			if( j - A - 1 >= 0 ){
				S.erase(S.find(dp[i][j-A-1]));
			}
			// cond: S has [j-A,j+B]
			dp[i+1][j] = *S.begin();
		}

		for(int j = 0 ; j <= w ; j++){
			dp[i+1][j] += abs(a[i]-j);
		}
	}
	for(int i = 0 ; i <= n ; i++){
		for(int j = 0 ; j < 10 ; j++){
			cout << dp[i][j] << " ";
		}
		cout << endl;
	}
	cout << *min_element(dp[n],dp[n]+w+1) << endl;
}

Submission Info

Submission Time
Task E - NarrowRectangles
User kyuridenamida
Language C++14 (GCC 5.4.1)
Score 0
Code Size 867 Byte
Status RE
Exec Time 476 ms
Memory 8960 KB

Judge Result

Set Name Sample Subtask All
Score / Max Score 0 / 0 0 / 300 0 / 700
Status
WA × 4
RE × 1
WA × 13
WA × 17
RE × 20
Set Name Test Cases
Sample 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 0_004.txt
Subtask 0_000, 0_001, 0_004, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt
All 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 0_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 2_018.txt, 2_019.txt, 2_020.txt, 2_021.txt, 2_022.txt, 2_023.txt, 2_024.txt, 2_025.txt, 2_026.txt, 2_027.txt, 2_028.txt, 2_029.txt, 2_030.txt, 2_031.txt, 2_032.txt, 2_033.txt, 2_034.txt, 2_035.txt, 2_036.txt
Case Name Status Exec Time Memory
0_000.txt WA 8 ms 764 KB
0_001.txt WA 1 ms 256 KB
0_002.txt WA 1 ms 256 KB
0_003.txt RE 466 ms 8192 KB
0_004.txt WA 1 ms 256 KB
1_005.txt WA 12 ms 896 KB
1_006.txt WA 12 ms 896 KB
1_007.txt WA 12 ms 896 KB
1_008.txt WA 18 ms 896 KB
1_009.txt WA 18 ms 896 KB
1_010.txt WA 18 ms 896 KB
1_011.txt WA 18 ms 896 KB
1_012.txt WA 18 ms 896 KB
1_013.txt WA 18 ms 896 KB
1_014.txt WA 18 ms 896 KB
1_015.txt WA 18 ms 896 KB
1_016.txt WA 18 ms 896 KB
1_017.txt WA 18 ms 896 KB
2_018.txt RE 162 ms 1664 KB
2_019.txt RE 161 ms 1664 KB
2_020.txt RE 195 ms 8960 KB
2_021.txt RE 216 ms 8960 KB
2_022.txt RE 214 ms 8960 KB
2_023.txt RE 215 ms 8960 KB
2_024.txt RE 215 ms 8960 KB
2_025.txt RE 215 ms 8960 KB
2_026.txt RE 213 ms 8960 KB
2_027.txt RE 218 ms 8960 KB
2_028.txt RE 216 ms 8960 KB
2_029.txt RE 215 ms 8960 KB
2_030.txt RE 216 ms 8960 KB
2_031.txt RE 186 ms 1664 KB
2_032.txt RE 187 ms 1664 KB
2_033.txt RE 189 ms 1664 KB
2_034.txt RE 476 ms 2176 KB
2_035.txt RE 216 ms 8960 KB
2_036.txt RE 216 ms 8960 KB