제출 #1163587

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163587		i271828	Akcija (COCI21_akcija)	C++20	0 / 110	4 ms	328 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int MAX=2005;

bool comp(pii a,pii b){
	if (a.second==b.second) return a.first<b.first;
	return a.second<b.second;
}

int N=4;
int K=3;
pii prods[MAX]={{1,1},{10,1},{2,3},{10,3}};
vector<int> W[MAX];
pair<int,pii> dp[MAX];

int main(){
	//*
	cin>>N>>K;
	for (int i=0;i<N;i++) cin>>prods[i].first>>prods[i].second;/**/
	sort(prods,prods+N,comp);
	for (int i=0;i<N;i++){
		W[prods[i].second].push_back(prods[i].first);
	}
	dp[0]={0,{0,0}};
	for (int d=1;d<=N;d++){
		dp[d]=dp[d-1];
		int val=0;
		int i=d;
		for (int j=d-1;j>=0;j--){
			while (i>j && d-i<W[d].size()){
				val+=W[d][d-i];
				i--;
			}
			if (d-i+dp[j].first > dp[d].first || ((d-i+dp[j].first == dp[d].first) && val+dp[j].second.first < dp[d].second.first)){
				dp[d]={dp[j].first+d-i, {dp[j].second.second+val, d}};
			}
		}
	}
	cout<<dp[N].first<<' '<<dp[N].second.first<<'\n';
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 30
• Subtask 6: 0 / 20