Submission #25554

#	Time	Username	Problem	Language	Result	Execution time	Memory
25554		zigui	스트랩 (JOI14_straps)	C++14	100 / 100	26 ms	32540 KiB

straps

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MX = 2005;

ll T[MX][MX];
pii D[MX];
int N;

int main()
{
	scanf("%d", &N);
	for(int i = 1; i <= N; i++) scanf("%d%d", &D[i].first, &D[i].second), D[i].first--;
	sort(D+1, D+N+1);
	reverse(D+1, D+N+1);
	for(int i = 2; i <= N; i++) T[0][i] = -2e9;
	for(int i = 1; i <= N; i++){
		for(int j = 0; j <= N; j++) T[i][j] = T[i-1][j];
		for(int j = 0; j <= N; j++){
			int w = j + D[i].first;
			if( w < 0 ) continue;
			if( w > N ) w = N;
			T[i][w] = max(T[i][w], T[i-1][j] + D[i].second);
		}
	}
	ll mx = 0;
	for(int i = 0; i <= N; i++) mx = max(mx, T[N][i]);
	printf("%lld\n", mx);
}

Compilation message (stderr)

straps.cpp: In function 'int main()':
straps.cpp:20:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
straps.cpp:21:84: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= N; i++) scanf("%d%d", &D[i].first, &D[i].second), D[i].first--;
                                                                                    ^

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 45 / 45
• Subtask 4: 45 / 45