Submission #1242980

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242980		altern23	Olympiads (BOI19_olympiads)	C++20	13 / 100	1300 ms	327680 KiB

olympiads

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

#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const int MAXN = 5e2;
const ll INF = 1e18;
const int MOD = 998244353;
const ld eps = 1e-6;

ll a[MAXN + 5][10];
priority_queue<pair<ll, vector<ll>>, vector<pair<ll, vector<ll>>>, greater<pair<ll, vector<ll>>>> dp[MAXN + 5][10];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);		
	int tc = 1;	
	// cin >> tc;
	for(;tc--;){
		ll N, K, C; cin >> N >> K >> C;
		for(int i = 1; i <= N; i++){
			for(int j = 0; j < K; j++){
				cin >> a[i][j];
			}
		}
		
		vector<ll> cur(K);
		dp[0][0].push({0, cur});
		for(int i = 1; i <= N; i++){
			for(int j = 0; j <= K; j++){	
				priority_queue<pair<ll, vector<ll>>, vector<pair<ll, vector<ll>>>, greater<pair<ll, vector<ll>>>> ndp;
				if(j){			
					dp[i][j] = dp[i - 1][j - 1];
					for(;!dp[i][j].empty();){
						auto x = dp[i][j].top(); dp[i][j].pop();
						vector<ll> nxt(K);
						ll sum = x.fi;
						for(int aa = 0; aa < K; aa++){
							if(a[i][aa] > x.sec[aa]){
								sum += a[i][aa] - x.sec[aa];
								nxt[aa] = a[i][aa];
							}
							else nxt[aa] = x.sec[aa];
						}
						ndp.push({sum, nxt});
						while((int)ndp.size() > C) ndp.pop();
					}
					ndp.swap(dp[i][j]);
				}
				for(;!dp[i - 1][j].empty();){
					dp[i][j].push(dp[i - 1][j].top());
					ndp.push(dp[i - 1][j].top());
					dp[i - 1][j].pop();
					while((int)dp[i][j].size() > C) dp[i][j].pop();
				}
				ndp.swap(dp[i - 1][j]);
			}
		}
		
		cout << dp[N][K].top().fi << "\n";
	}
}

• Subtask 1: 13 / 13
• Subtask 2: 0 / 31
• Subtask 3: 0 / 24
• Subtask 4: 0 / 32