oj.uz

Submission #943898

# Submission time Handle Problem Language Result Execution time Memory
943898 2024-03-12T04:05:42 Z penguin133 Potatoes and fertilizers (LMIO19_bulves) C++17
20 / 100
 1000 ms 7516 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int dp[2][30005];
int n, A[500005], B[500005];

void solve(){
	cin >> n;
	for(int i = 1; i <= n; i++)cin >> A[i] >> B[i], A[i] -= B[i], A[i] += A[i - 1];
	for(int i = 1; i <= n; i++){
		for(int j = 0; j <= 30000; j++){
			if(j)dp[i & 1][j] = min(dp[i & 1][j - 1], dp[(i - 1) & 1][j] + abs(A[i] - j));
			else dp[i & 1][j] = dp[(i - 1) & 1][j] + abs(A[i] - j);
		}
	}
	cout << dp[n & 1][A[n]];
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message

bulves.cpp:29:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   29 | main(){
      | ^~~~

Subtask #1
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 278 ms 2996 KB Output is correct
3 Correct 276 ms 2904 KB Output is correct
4 Execution timed out 1062 ms 7516 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 278 ms 2996 KB Output is correct
3 Correct 276 ms 2904 KB Output is correct
4 Execution timed out 1062 ms 7516 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 278 ms 2996 KB Output is correct
3 Correct 2 ms 2904 KB Output is correct
4 Correct 94 ms 2980 KB Output is correct
5 Correct 141 ms 2908 KB Output is correct
6 Correct 276 ms 2904 KB Output is correct
7 Correct 277 ms 3156 KB Output is correct
8 Correct 276 ms 2904 KB Output is correct
9 Correct 277 ms 2908 KB Output is correct
10 Correct 276 ms 2904 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 278 ms 2996 KB Output is correct
3 Correct 276 ms 2904 KB Output is correct
4 Correct 2 ms 2904 KB Output is correct
5 Correct 94 ms 2980 KB Output is correct
6 Correct 141 ms 2908 KB Output is correct
7 Correct 276 ms 2904 KB Output is correct
8 Correct 277 ms 3156 KB Output is correct
9 Correct 276 ms 2904 KB Output is correct
10 Correct 277 ms 2908 KB Output is correct
11 Correct 276 ms 2904 KB Output is correct
12 Runtime error 188 ms 5572 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 278 ms 2996 KB Output is correct
3 Correct 276 ms 2904 KB Output is correct
4 Correct 2 ms 2904 KB Output is correct
5 Correct 94 ms 2980 KB Output is correct
6 Correct 141 ms 2908 KB Output is correct
7 Correct 276 ms 2904 KB Output is correct
8 Correct 277 ms 3156 KB Output is correct
9 Correct 276 ms 2904 KB Output is correct
10 Correct 277 ms 2908 KB Output is correct
11 Execution timed out 1062 ms 7516 KB Time limit exceeded
12 Halted 0 ms 0 KB -