Submission #1281302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281302		hynmj	Topical (NOI23_topical)	C++20	100 / 100	317 ms	77664 KiB

Main

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int MAXN = 1e6+1, MOD = 1e9+7;

int N, A;
ll ans, dp[20];
vector <int> prime[MAXN];
vector <pii> power[MAXN];

int main () {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
   ll n, k, ans = 0;
   cin >> n >> k;
   vector<vector<pair<int,int>>> topics(k, vector<pair<int,int>> (n));
   vector<vector<int>> w(n, vector<int>(k)); 
   for(int i = 0; i <n; i++){
     for(int j = 0; j < k; j++){
       cin >> topics[j][i].first;
       topics[j][i].second = i;
     }
   }
    for(int i = 0; i <n; i++){
     for(int j = 0; j < k; j++){
       cin >> w[i][j];
     }
   }
   for(int i = 0 ;i < k; i++){
     sort(topics[i].begin(), topics[i].end());
   }
   vector<ll> cnt(n), sz(k), track(k), tmp;
   while(1){
     for(int i = 0; i< k; i++){
       while(track[i] < n and sz[i] >= topics[i][track[i]].first){
          cnt[topics[i][track[i]].second]++;
          track[i]++;
          if(cnt[topics[i][track[i] - 1].second] == k){ 
            tmp.push_back(topics[i][track[i] - 1].second);
          }
       }
     }
     if(tmp.empty()){// can't further process
       break;
     }
     else{
       for(auto i : tmp){
         for(int j = 0; j < k; j ++){
           sz[j] += w[i][j];
         }
         ans++;
       }
       tmp.clear();
     }
   }
   cout << ans << '\n';
   
}

• Subtask 1: 12 / 12
• Subtask 2: 28 / 28
• Subtask 3: 21 / 21
• Subtask 4: 39 / 39