Submission #234558

#	Time	Username	Problem	Language	Result	Execution time	Memory
234558		shayan_p	Segway (COI19_segway)	C++14	100 / 100	182 ms	61432 KiB

segway

// Never let them see you bleed...

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

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

const int maxn = 2e4 + 10, maxL = 310, maxS = 55, maxT = maxL * maxS, inf = 1e9;

int a[maxn][3], ans[maxn], cnt[maxL], suf[maxL];
int super[maxn], supercnt[maxn];
bool is[maxL];
vector<pii> v[maxT];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    fill(super, super+maxn, -inf);
    
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
	cin >> a[i][0] >> a[i][1] >> a[i][2];
	v[a[i][0]].PB({i, 1});
    }
    int q;
    cin >> q;
    while(q--){
	int x;
	cin >> x;
	is[x] = 1;		 
    }
    cnt[0] = n;
    for(int t = 0; t < maxT; t++){	
	for(int i = maxL-1; i >= 0; i--)
	    suf[i] = suf[i+1] + cnt[i];
	for(pii p : v[t]){
	    if(p.S == 300){
		ans[p.F] = t;
		continue;
	    }
	    if(is[p.S]){
		int T = suf[p.S] % 20;
		if(super[p.F] + supercnt[p.F] <= t)
		    super[p.F] = t, supercnt[p.F] = T;
	    }
	    cnt[p.S-1]--;
	    cnt[p.S]++;
	    if(super[p.F] + supercnt[p.F] > t)
		v[t + 1].PB({p.F, p.S+1});
	    else
		v[t + (p.S < 100 ? a[p.F][0] : (p.S < 200 ? a[p.F][1] : a[p.F][2]))].PB({p.F, p.S+1});
	}
    }
    for(int i = 0; i < n; i++){
	cout << ans[i] << "\n";
    }
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 45 / 45