Submission #1041553

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041553		vjudge1	Segway (COI19_segway)	C++98	0 / 100	2 ms	1372 KiB

segway

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
using namespace std;
#define int long long 
const int N = 100001;
const int mod = 1e9+7;
const int mod1 = 998244353;

void solve(){
    int n;cin >>n;
    vector<vector<int>> v(n+1,vector<int>(3));
    for(int i = 1 ; i<=n; i++)
        cin >> v[i][0] >> v[i][1] >> v[i][2];
    int m;cin >> m;
    vector<int> acc(m+1);
    for(int i = 1;i<= m ;i ++){
        cin >> acc[i];
    }
    vector<vector<int>> time(n+1,vector<int>(301));
    vector<vector<int>> rem(n+1,vector<int>(301));
    int p = 1;
    for(int j = 1 ;j <=300 ;j ++){
        vector<int> o;
        for(int i = 1;i<=n ;i ++){
            int sp = v[i][(j-1)/100];
            // if(rem[i][j-1] > 1){
            //     time[i][j] = time[i][j-1] + 1;
            //     rem[i][j] = rem[i][j-1]-1;
            // }
            if(time[i][j]== 0)
                time[i][j] = time[i][j-1] + sp;
            else 
                time[i][j] = min(time[i][j],time[i][j-1] + sp);
            o.push_back(time[i][j]);
        }
        if(p<=m and acc[p] == j){
            sort(o.begin(),o.end());
            // for(int it:o)cout<<it<<" ";
            // cout<<endl;
            for(int i = 1;i<= n; i++){
                // if(j+1<=300 and rem[i][j+1] > 0)continue;
                int t = upper_bound(o.begin(),o.end(),time[i][j-1])-o.begin();
                // cout<<t<<" "<<time[i][j-1]<<endl;
                // if(t>=o.size())t--;
                int p = (t)%20;
                for(int k = j+1 ;k <= min(300ll,j+p) ; k++){
                    // if(i == 3){
                    //     cout<<k<<"T";
                    // }
                    rem[i][k] = 1;
                    time[i][k] = time[i][k-1] + 1;
                }
                // cout<<endl;
            }
        }
        if(p<=m and acc[p] == j)p++;
    }
    // cout<<time[3][102]<<endl;
    for(int i = 1;i<= n;i ++){
        cout<<time[i][300]<<endl;
    }
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);cout.tie(NULL);
    
    int t=1;
    // cin>>t;
    cout<<setprecision(16);
    while(t--){
        solve();
    }
}

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