Submission #768427

#	Time	Username	Problem	Language	Result	Execution time	Memory
768427		setytousi	Arranging Tickets (JOI17_arranging_tickets)	C++14	45 / 100	6011 ms	1180 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], seg[MAXN << 2];
set<pair<pii, int>> st;

void add(int l, int r, int val, int s = 0, int e = n, int v = 1){
    if (r <= s || e <= l) return;
    if (l <= s && e <= r) {
        seg[v] += val;
        return;
    }
    int mid = (s + e) >> 1, lc = v << 1, rc = lc | 1;
    add(l, r, val, s, mid, lc);
    add(l, r, val, mid, e, rc);
}
int get(int ind, int s = 0, int e = n, int v = 1){
    if (s + 1 == e) return seg[v];
    int mid = (s + e) >> 1, lc = v << 1, rc = lc | 1;
    if (ind < mid) return get(ind, s, mid, lc) + seg[v];
    else return get(ind, mid, e, rc) + seg[v];
}

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)){
            // cout << i << ' ' << get(i) << ' ' << get(0) << endll;
            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;
            // cout << "hazf" << ' ' << a << ' ' << b << ' ' << c << endll;
            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(seg, seg + (MAXN << 2), 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: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 15