oj.uz

Submission #782600

# Submission time Handle Problem Language Result Execution time Memory
782600 2023-07-14T06:20:00 Z qwerasdfzxcl 코알라 (JOI13_koala) C++17
20 / 100
 2000 ms 3720 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr ll INF = 4e18;
int X[100100], B[100100];
ll dp[100100];

int main(){
	int _s, _e, k, A, n;
	scanf("%d %d %d %d %d", &_s, &_e, &k, &A, &n);

	X[0] = _s;
	X[n+1] = _e;

	for (int i=1;i<=n;i++){
		scanf("%d %d", X+i, B+i);
	}

	vector<int> C;
	for (int i=0;i<=n+1;i++){
		C.push_back(X[i] % k);
	}

	sort(C.begin(), C.end());
	C.erase(unique(C.begin(), C.end()), C.end());

	for (int i=1;i<=n+1;i++){
		dp[i] = -INF;
		for (int j=0;j<i;j++){
			if (X[i] % k > X[j] % k){
				dp[i] = max(dp[i], (dp[j] + (ll)(X[j]/k) * A) - ((ll)(X[i]/k) * A + A - B[i]));
			}
			else{
				// if (i==3 && j==1) printf("okok %lld %d %d %d\n", dp[j], X[j]/k, X[i]/k, B[i]);
				// if (i==3 && j==1) printf("okokok %lld %lld\n", (dp[j] + (ll)(X[j]/k) * A), ((ll)(X[i]/k) * A - B[i]));
				// if (i==3 && j==1) printf("okokokok %lld <- %lld\n", dp[i], (dp[j] + (ll)(X[j]/k) * A) - ((ll)(X[i]/k) * A - B[i]));
				dp[i] = max(dp[i], (dp[j] + (ll)(X[j]/k) * A) - ((ll)(X[i]/k) * A - B[i]));
			}
		}

		// printf("%d -> %lld\n", i, dp[i]);
	}

	printf("%lld\n", dp[n+1]);
}

Compilation message

koala.cpp: In function 'int main()':
koala.cpp:11:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |  scanf("%d %d %d %d %d", &_s, &_e, &k, &A, &n);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
koala.cpp:17:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |   scanf("%d %d", X+i, B+i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 3 ms 320 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 5 ms 340 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 4 ms 340 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2048 ms 3676 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2053 ms 3720 KB Time limit exceeded
2 Halted 0 ms 0 KB -