Submission #1238431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238431		ksu2009en	Longest Trip (IOI23_longesttrip)	C++20	Compilation error	0 ms	0 KiB

longesttrip

#include "closing.h"

#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>
#include <unordered_map>

using namespace std;
typedef long long ll;

ll n, x, y, k;

vector<pair<ll, ll>> d[3007];

int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W){
    n = N, x = X, y = Y, k = K;
    
    if(x > y)
        swap(x, y);
    
    vector<ll> w(n);
    
    for(int i = 0; i < n - 1; i++){
        d[U[i]].push_back({V[i], W[i]});
        d[V[i]].push_back({U[i], W[i]});
        
        w[min(U[i], V[i])] = W[i];
    }
    
    vector<ll> a(n), b(n), c(n);

    for(int i = x - 1; i >= 0; i--)
        a[i] = a[i + 1] + w[i];
    
    for(int i = x + 1; i < n; i++)
        a[i] = a[i - 1] + w[i - 1];
    
    for(int i = y - 1; i >= 0; i--)
        b[i] = b[i + 1] + w[i];
    
    for(int i = y + 1; i < n; i++)
        b[i] = b[i - 1] + w[i - 1];
    
    for(int i = 0; i < n; i++)
        c[i] = max(a[i], b[i]);
    
    vector<ll> p1(n), p2(n), p3(n);
    
    for(int i = 0; i < n; i++){
        if(i != 0){
            p1[i] = p1[i - 1],
            p2[i] = p2[i - 1],
            p3[i] = p3[i - 1];
        }
        
        p1[i] += a[i];
        p2[i] += b[i];
        p3[i] += c[i];
    }
    
    ll ans  = 0;
    
    for(int i = 0; i < n; i++){
        vector<pair<ll, ll>> vec;
        vector<ll> ind(n, -1);
        
        for(int j = min((int)x, i - 1); j >= 0; j--)
            vec.push_back({a[j], j});
        
        for(int j = max((int)y, i + 1); j < n; j++)
            vec.push_back({b[j], j});

        sort(vec.begin(), vec.end());
        
        for(int j = 0; j < (ll)(vec.size()); j++)
            ind[vec[j].second] = j;
        
        ll cur = -1, sum = 0, cnt = 0, non_del = 0;
        
        if(i > x)
            cnt += p1[i - 1] - p1[x];
        if(i < y)
            cnt += p2[y] - (i != 0 ? p2[i - 1] : 0);
        
//        if(i == 3){
//            for(auto j: vec)
//                cout << j.first << ' ' << j.second << endl;
//        }
        
        for(int j = i; j < n; j++){
            cnt += c[j];
            
            if(j <= y)
                cnt -= b[j];
            
//            if(i == 3){
//                cout << "cnt    " << j << ' ' << cnt << endl;
//            }
            
            if(ind[j] != -1){
                vec[ind[j]].second = -1;
                
                if(ind[j] <= cur){
                    sum -= vec[ind[j]].first;
                    non_del--;
                }
            }
            
            if(y < i || j < x)
                continue;
            
            while(cur + 1 < vec.size()){
                if(vec[cur + 1].second == -1){
                    cur++;
                    continue;
                }
                
                if(cnt + vec[cur + 1].first + sum <= k){
                    sum += vec[cur + 1].first;
                    cur++;
                    
                    non_del++;
                }
                else
                    break;
            }
            
            while(cur >= 0 && cnt + sum > k){
                if(vec[cur].second == -1){
                    cur--;
                    continue;
                }
                
                sum -= vec[cur].first;
                cur--;
                
                non_del--;
            }
            
            if(cnt + sum <= k){
//                cout << " !! " << i << ' ' << j << ' ' << cur << ' ' << sum << ' ' << non_del << endl;
                ans = max(ans, (j - i + 1) * 2 + non_del);
                
//                cout << "      ANS       " << i << ' ' << j << " CNT : " << cnt << endl;
//                if(ans == 6){
//                }
            }
        }
    }
    
    return ans;
}

/*
 
 1
 7 2 4 8
 0 1 2
 1 2 3
 2 3 4
 3 4 2
 4 5 5
 5 6 3
 
 1
 7 2 4 24
 0 1 2
 1 2 3
 2 3 4
 3 4 2
 4 5 5
 5 6 3
 
 */

Compilation message (stderr)

longesttrip.cpp:1:10: fatal error: closing.h: No such file or directory
    1 | #include "closing.h"
      |          ^~~~~~~~~~~
compilation terminated.