oj.uz

답안 #404814

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
404814 2021-05-15T05:08:08 Z LptN21 Salesman (IOI09_salesman) C++17
100 / 100
 290 ms 15940 KB 
#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
#define FF first
#define SS second
#define pb push_back
#define sz(x) (int)x.size()
#define oo 1e9
#define eps 1e-9
#define PI acos(-1.0)
#define lb lower_bound
#define ub upper_bound
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;
const int N = 5e5+7, M=2e5+7;
const int MOD = 1e9+7;

int n, m, k, t;

struct fair{
    int t, l, m;
    int best, cbest, bbest;
    bool operator<(const fair &p) const {
        if(t==p.t) return l<p.l;
        return t<p.t;
    }
} f[N];

int fen[N][2];
// 0 : U, 1 : D
void add(int j, int i, int v) {for(;i<N;i+=i&-i) fen[i][j]=max(fen[i][j], v);}
int get(int j, int i) {
    int res=-oo;
    for(;i>0;i-=i&-i) res=max(res, fen[i][j]);
    return res;
}
int cost(int p1, int p2) { // p1 -> p2
    if(p1<p2) return (p2-p1)*k;
    return (p1-p2)*m;
}
void upd(int idx) {
    add(0, f[idx].l, f[idx].best+f[idx].l*k), add(1, N-f[idx].l, f[idx].best-f[idx].l*m);
}
int qry(int idx) {
    return f[idx].m+max(get(0, f[idx].l)-f[idx].l*k, get(1, N-f[idx].l)+f[idx].l*m);
}

signed main() {
    //freopen("test.inp", "r", stdin);
    //freopen("test.out", "w", stdout);
    //fastIO;
    scanf("%d%d%d%d", &n, &m, &k, &t);
    // m : u, k : d
    for(int i=0;i<N;i++) for(int j=0;j<2;j++) fen[i][j]=-oo;
    for(int i=1;i<=n;i++) scanf("%d%d%d", &f[i].t, &f[i].l, &f[i].m);
    sort(f+1, f+n+1);f[n+1].l=f[0].l=t, f[n+1].m=f[0].best=0;
    upd(0);
    for(int i=1;i<=n;i++) {
        if(i==n||f[i].t!=f[i+1].t) f[i].best=qry(i), upd(i);
        else {
            int l=i++, r;
            while(i<=n&&f[i].t==f[l].t) i++;
            r=--i;
            for(int j=l;j<=r;j++) f[j].bbest=f[j].best=qry(j);
            // U -> D
            f[l].cbest=f[l].bbest;
            for(int j=l+1;j<=r;j++) {
                f[j].cbest=max(f[j-1].cbest-cost(f[j-1].l, f[j].l)+f[j].m, f[j].bbest);
                f[j].best=max(f[j].best, f[j].cbest);
            }
            // D -> U
            f[r].cbest=f[r].bbest;
            for(int j=r-1;j>=l;j--) {
                f[j].cbest=max(f[j+1].cbest-cost(f[j+1].l, f[j].l)+f[j].m, f[j].bbest);
                f[j].best=max(f[j].best, f[j].cbest);
            }
            for(int j=l;j<=r;j++) upd(j);
        }
    }
    printf("%d", max(0, qry(n+1)));
    return 0;
}
/* stuff you should look for
    - int overflow, array bounds
    - special cases (n=1?)
    - do smth instead of do nothing and stay organized
    - WRITE STUFF DOWN
    - DONT JUST STICK ON ONE APPROACH
*/

Compilation message

salesman.cpp: In function 'int main()':
salesman.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |     scanf("%d%d%d%d", &n, &m, &k, &t);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:56:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     for(int i=1;i<=n;i++) scanf("%d%d%d", &f[i].t, &f[i].l, &f[i].m);
      |                           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4172 KB Output is correct
2 Correct 3 ms 4172 KB Output is correct
3 Correct 3 ms 4172 KB Output is correct
4 Correct 4 ms 4172 KB Output is correct
5 Correct 5 ms 4340 KB Output is correct
6 Correct 14 ms 4688 KB Output is correct
7 Correct 32 ms 5288 KB Output is correct
8 Correct 65 ms 6444 KB Output is correct
9 Correct 82 ms 7620 KB Output is correct
10 Correct 154 ms 11188 KB Output is correct
11 Correct 163 ms 11164 KB Output is correct
12 Correct 236 ms 13676 KB Output is correct
13 Correct 228 ms 13568 KB Output is correct
14 Correct 281 ms 15928 KB Output is correct
15 Correct 248 ms 15836 KB Output is correct
16 Correct 270 ms 15836 KB Output is correct
17 Correct 3 ms 4172 KB Output is correct
18 Correct 3 ms 4172 KB Output is correct
19 Correct 3 ms 4172 KB Output is correct
20 Correct 4 ms 4172 KB Output is correct
21 Correct 4 ms 4172 KB Output is correct
22 Correct 5 ms 4300 KB Output is correct
23 Correct 7 ms 4300 KB Output is correct
24 Correct 5 ms 4300 KB Output is correct
25 Correct 55 ms 6520 KB Output is correct
26 Correct 109 ms 8900 KB Output is correct
27 Correct 183 ms 12356 KB Output is correct
28 Correct 211 ms 12424 KB Output is correct
29 Correct 290 ms 15940 KB Output is correct
30 Correct 267 ms 15920 KB Output is correct