Submission #1225233

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225233		salmon	Sparklers (JOI17_sparklers)	C++20	50 / 100	43 ms	10052 KiB

sparklers

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

int N,K;
long long int T;
long long int memo[1100][1100];
int lst[1100];

int main(){
	
	scanf(" %d",&N);
	scanf(" %d",&K);
	scanf(" %lld",&T);
	
	for(int i = 1; i <= N; i++) scanf(" %d",&lst[i]);
	
	int s = 0;
	int e = 1e9;

	while(s != e){
		int m = (s + e)/2;
		
		for(int i = 1; i <= N; i++){
			for(int j = 1; j <= N; j++){
				memo[i][j] = -1;
			}
		}
		
		m *= 2;
		
		memo[K][K] = T * m;
		
		for(int s = 1; s <= N - 1; s++){
			for(int i = 1; i + s <= N; i++){
				if(lst[i + 1] - lst[i] <= memo[i + 1][i + s]) memo[i][i + s] = max(memo[i][i + s],memo[i + 1][i + s] - (lst[i + 1] - lst[i])  + T * m);
				if(lst[i + s] - lst[i + s - 1] <= memo[i][i + s - 1])   memo[i][i + s] = max(memo[i][i + s],memo[i][i + s - 1] - (lst[i + s] - lst[i + s - 1])  + T * m);
			}
		}
		
		m/=2;
		
		/*printf("%d\n",m);
		for(int i = 1; i <= N; i++){
			for(int j = 1; j <= N; j++){
				printf("%lld ",memo[i][j]);
			}
			printf("\n");
		}*/
		
		if(memo[1][N] == -1){
			s = m + 1;
		}
		else e = m;
	}
	
	printf("%d\n",s);
	
}

Compilation message (stderr)

sparklers.cpp: In function 'int main()':
sparklers.cpp:11:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
sparklers.cpp:12:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |         scanf(" %d",&K);
      |         ~~~~~^~~~~~~~~~
sparklers.cpp:13:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |         scanf(" %lld",&T);
      |         ~~~~~^~~~~~~~~~~~
sparklers.cpp:15:42: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         for(int i = 1; i <= N; i++) scanf(" %d",&lst[i]);
      |                                     ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 0 / 50