Submission #577556

#	Time	Username	Problem	Language	Result	Execution time	Memory
577556		balbit	Treatment Project (JOI20_treatment)	C++14	35 / 100	3072 ms	10924 KiB

treatment

#include <bits/stdc++.h>
using namespace std;
#define int ll
#define ll long long
#define pii pair<ll, ll>
#define f first
#define s second

#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(), (x).end()
#define pb push_back

#define MX(a,b) a =  max(a,b)
#define MN(a,b) a =  min(a,b)
#define FOR(i,a,b) for (int i = a; i<b; ++i)
#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<"- "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y){cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT


const int maxn = 3e5+5;
const int mod = 1e9+7;
const ll inf = 0x3f3f3f3f3f3f3f3f;

struct rect{
    int x,y,r,c,i;

    bool operator < (rect &R) {
        if (y != R.y) return y < R.y;
        return x < R.x;
    }
};

bool isbeg[maxn], isend[maxn]; // for each rectangle, is it the beg or end?????
bool done[maxn];
ll dst[maxn];

ll get(vector<rect> v) {
    for (rect &R : v) {
        bug(R.x,R.y,R.r,R.c,R.i);
        bug(isbeg[R.i]);
        bug(isend[R.i]);
    }

//    sort(ALL(v));

    memset(dst, 0x3f, sizeof dst);
    int n = SZ(v);
    for (rect &R : v) {
        if (isbeg[R.i]) {
            dst[R.i] = R.c;

        }
    }

    ll re = inf;
    REP(round, SZ(v)) {
        int go = -1, mnd = inf;
        REP(i,n)  {
            if (!done[i] && dst[i] < mnd) {
                mnd = dst[i]; go = i;
            }
        }
        if (go == -1) break;
        done[go] = 1;
        if (isend[go]) {
            MN(re, mnd);
        }

        REP(j,n) {
            if (!done[j]) {
                // test if i can update him
                if (v[go].x + v[go].r + 1 >= v[j].x &&
                    v[go].y + v[go].r + 1 >= v[j].y
                    ) {
                    MN(dst[j], dst[go] + v[j].c);
                }
            }
        }

    }
    if (re == inf) re = -1;
    return re;
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    bug(1,2);

    vector<rect> go;
    int n,m; cin>>n>>m;
    REP(i,m) {
        int t,l,r,c; cin>>t>>l>>r>>c;
        --l; --r;
        isbeg[i] = l == 0;
        isend[i] = r == n-1;
        go.pb({l+t, l-t,r-l,c,i});
    }

    ll re =get(go);
    cout<<re<<endl;

}

/*
10 5
1 8 10 30
1 1 6 50
2 7 7 100
3 5 7 11
2 8 8 11



7 6 10 4
4 1 3 1
*/

Compilation message (stderr)

treatment.cpp: In function 'long long int get(std::vector<rect>)':
treatment.cpp:47:16: warning: unused variable 'R' [-Wunused-variable]
   47 |     for (rect &R : v) {
      |                ^

• Subtask 1: 0 / 4
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 0 / 61