Submission #768440

#	Time	Username	Problem	Language	Result	Execution time	Memory
768440		setytousi	Arranging Tickets (JOI17_arranging_tickets)	C++14	65 / 100	2133 ms	4652 KiB

arranging_tickets

#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <iomanip>
#include <cassert>
#include <cstring>
#include <sstream>
#include <numeric>
#include <cstdio>
#include <bitset>
#include <math.h>
#include <assert.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
 
const ll MAXN = 3e3 + 10;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
 
#define fast_io     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io     freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define pb          push_back
#define F           first
#define S           second
#define Sz(x)       int((x).size())
#define all(x)      (x).begin(), (x).end()
#define cl          clear()
#define endll       '\n'

vector<pair<pii, int>> reqs;
vector<int> vec;
vector<pii> open[MAXN];
int n, m, ind[MAXN], fen[MAXN];
set<pair<pii, int>> st;

inline void ad(int f, int val){
    f += 5;
    for (; f < MAXN; f += f & -f) fen[f] += val;
}
inline int get(int f){
    int ans = 0;
    f += 5;
    for (; f; f -= f & -f) ans += fen[f];
    return ans;
}
inline void add(int l, int r, int val){
    r--;
    ad(l, val);
    ad(r + 1, -val);
}


inline int check(){
    for (int i = n - 1; i >= 1; i--){
        for (auto r : open[i]){
            st.insert({{r.F, i}, r.S});
        }
        while(get(i) > get(0)){
            if (st.empty()) return 1000000000;
            pair<pii, int> r = *(st.begin());
            st.erase(st.begin());
            int a = r.F.F, b = r.F.S, c = r.S;
            if (c < (get(i) - get(0) + 1) / 2){
                add(a + 1, b + 1, -c);
                add(0, a + 1, c);
                add(b + 1, n, c);
            }
            else{
                int val = (get(i) - get(0) + 1) / 2;
                add(a + 1, b + 1, -val);
                add(0, a + 1, val);
                add(b + 1, n, val);
                st.insert({{a, b}, c - val});
            }
        }
    }
    return get(0);
}

int main(){
    fast_io;
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        reqs.pb({{a, b}, c});
    }
    int ans = 1000000000;
    for (int i = 1; i <= n; i++){
        st.cl;
        fill(fen, fen + MAXN, 0);
        for (int j = 0; j <= n; j++) open[j].cl;
        vec.cl;
        for (int j = i; j <= n; j++) vec.pb(j);
        for (int j = 1; j < i; j++) vec.pb(j);
        for (int j = 0; j < n; j++) ind[vec[j]] = j;
        for (auto x : reqs){
            int a = x.F.F, b = x.F.S, c = x.S;
            if (ind[b] < ind[a]) swap(a, b);
            open[ind[b]].pb({ind[a], c});
            add(ind[a] + 1, ind[b] + 1, c);
        }
        ans = min(ans, check());
    }
    cout << ans << endll;
}

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