Submission #782600

#	Time	Username	Problem	Language	Result	Execution time	Memory
782600		qwerasdfzxcl	코알라 (JOI13_koala)	C++17	20 / 100	2053 ms	3720 KiB

koala

#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 (stderr)

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 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 50