Submission #1247574

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247574		nvujica	Overtaking (IOI23_overtaking)	C++20	29 / 100	34 ms	584 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second

using namespace std;

const int maxn = 105;

ll e[maxn][maxn];
ll t[maxn][maxn];
vector<ll> s;
vector<ll> w;

void init(int l, int n, vector<ll> poc, vector<int> W, int X, int m, vector<int> S){
    for(int i = 0; i < n; i++) t[i][0] = poc[i];
    
    for(auto x: S) s.push_back(x);
    for(auto x: W) w.push_back(x);
    w.push_back(X);

    return;
}

ll arrival_time(ll y){
    int m = s.size();
    int n = w.size() - 1;
//	cout << endl;
	
//	cout << "m: " << m << endl;
//	cout << "n: " << n << endl;
	
    t[n][0] = y;
	
//	for(int i = 0; i <= n; i++){
//		cout << t[i][0] << ' ';
//	}
//	cout << endl;
	
	queue<int> q;
	vector <pair<ll, int> > v;
	
    for(int j = 1; j < m; j++){
        v.clear();
        
        for(int i = 0; i <= n; i++){
            e[i][j] = t[i][j - 1] + w[i] * (s[j] - s[j - 1]);
            v.push_back({t[i][j - 1], i});
        }

        sort(v.begin(), v.end());
        
//        cout << "TU: ";

        ll naj = 0;

        for(int i = 0; i <= n; i++){
            ll vri = v[i].fi;
            int ind = v[i].se;
			
//			cout << ind << ' ';
			
            if(!i || vri != v[i - 1].fi){
//            	cout << "da " << ind << endl;
            	while(!q.empty()){
            		int x = q.front();
            		q.pop();
					naj = max(naj, e[x][j]);
//					cout << endl << ind << ' ' << x << endl;
				}
				q.push(ind);
			}
			else {
				q.push(ind);
			}

            t[ind][j] = max(naj, e[ind][j]);
        }
//        cout << endl;
        
        while(!q.empty()) q.pop();
        
//        for(int i = 0; i <= n; i++){
//        	cout << t[i][j] << ' ';
//		}
//		cout << endl;
    }

    return t[n][m - 1];
}

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 0 / 10
• Subtask 3: 20 / 20
• Subtask 4: 0 / 26
• Subtask 5: 0 / 35