oj.uz

답안 #404858

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
404858 2021-05-15T07:36:03 Z LptN21 Salesman (IOI09_salesman) C++14
100 / 100
 296 ms 16072 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 b, bb, cb;
    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 : UP, 1 : DOWN
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;}

void upd(int idx) {
    add(0, f[idx].l, f[idx].b+f[idx].l*k), add(1, N-f[idx].l, f[idx].b-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);
    // u : m, d : k
    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[0].b=f[n+1].m=0, f[0].l=f[n+1].l=t;upd(0);
    for(int i=1;i<=n;i++) {
        if(i==n||f[i].t!=f[i+1].t) f[i].b=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].bb=f[j].b=qry(j);
            // U -> D
            f[l].cb=f[l].bb;
            for(int j=l+1;j<=r;j++) {
                f[j].cb=max(f[j-1].cb-(f[j].l-f[j-1].l)*k+f[j].m, f[j].bb);
                f[j].b=max(f[j].cb, f[j].b);
            }
            // D -> U
            f[r].cb=f[r].bb;
            for(int j=r-1;j>=l;j--) {
                f[j].cb=max(f[j+1].cb-(f[j+1].l-f[j].l)*m+f[j].m, f[j].bb);
                f[j].b=max(f[j].cb, f[j].b);
            }
            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:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     scanf("%d%d%d%d", &n, &m, &k, &t);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:47:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     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 4 ms 4172 KB Output is correct
4 Correct 4 ms 4172 KB Output is correct
5 Correct 5 ms 4300 KB Output is correct
6 Correct 14 ms 4688 KB Output is correct
7 Correct 30 ms 5324 KB Output is correct
8 Correct 57 ms 6536 KB Output is correct
9 Correct 84 ms 7660 KB Output is correct
10 Correct 156 ms 11180 KB Output is correct
11 Correct 174 ms 11236 KB Output is correct
12 Correct 264 ms 13636 KB Output is correct
13 Correct 219 ms 13592 KB Output is correct
14 Correct 296 ms 15924 KB Output is correct
15 Correct 266 ms 16072 KB Output is correct
16 Correct 269 ms 15844 KB Output is correct
17 Correct 3 ms 4212 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 6 ms 4300 KB Output is correct
23 Correct 5 ms 4300 KB Output is correct
24 Correct 6 ms 4304 KB Output is correct
25 Correct 56 ms 6456 KB Output is correct
26 Correct 110 ms 8788 KB Output is correct
27 Correct 185 ms 12416 KB Output is correct
28 Correct 200 ms 12412 KB Output is correct
29 Correct 294 ms 15944 KB Output is correct
30 Correct 271 ms 15924 KB Output is correct