oj.uz

답안 #527823

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
527823 2022-02-18T12:57:43 Z mathking1021 Salesman (IOI09_salesman) C++17
62 / 100
 417 ms 37348 KB 
#include <iostream>
#include <cstdio>
#include <algorithm>
#define PLPLL pair<ll, PLL>
#define PLL pair<ll, ll>
#define F first
#define S second

using namespace std;
typedef long long ll;

const ll M = 1e18;

ll n, m, m1, m2, k;
PLPLL a[500005];
ll base = (1 << 19);
ll seg1[1100005];
ll seg2[1100005];

void update1(ll p, ll q)
{
    p += base;
    seg1[p] = q;
    p /= 2;
    while(p >= 1)
    {
        seg1[p] = max(seg1[p * 2], seg1[p * 2 + 1]);
        p /= 2;
    }
}

void update2(ll p, ll q)
{
    p += base;
    seg2[p] = q;
    p /= 2;
    while(p >= 1)
    {
        seg2[p] = max(seg2[p * 2], seg2[p * 2 + 1]);
        p /= 2;
    }
}

ll query1(ll p, ll q)
{
    p += base;
    q += base;
    ll re = -M;
    while(p < q)
    {
        if(p % 2 == 1) re = max(re, seg1[p]), p++;
        if(q % 2 == 0) re = max(re, seg1[q]), q--;
        p /= 2, q /= 2;
    }
    if(p == q) re = max(re, seg1[p]);
    return re;
}

ll query2(ll p, ll q)
{
    p += base;
    q += base;
    ll re = -M;
    while(p < q)
    {
        if(p % 2 == 1) re = max(re, seg2[p]), p++;
        if(q % 2 == 0) re = max(re, seg2[q]), q--;
        p /= 2, q /= 2;
    }
    if(p == q) re = max(re, seg2[p]);
    return re;
}

int main()
{
    scanf("%lld%lld%lld%lld", &n, &m1, &m2, &k);
    m = m1 + m2;
    for(ll i = 0; i < n; i++)
    {
        scanf("%lld%lld%lld", &a[i].F, &a[i].S.F, &a[i].S.S);
    }
    sort(a, a + n);
    for(ll i = 1; i < 2 * base; i++) seg1[i] = seg2[i] = -M;
    update1(k, 0 - k * m);
    update2(k, 0);
    for(ll i = 0; i < n; i++)
    {
        ll t1 = query1(a[i].S.F, base - 1);
        ll t2 = query2(0, a[i].S.F);
        ll t3 = t1 + a[i].S.F * m;
        ll t4 = max(t2, t3) + a[i].S.S;
        ll t5 = query1(a[i].S.F, a[i].S.F) + a[i].S.F * m;
        ll t6 = query2(a[i].S.F, a[i].S.F);
        update1(a[i].S.F, max(t5, t4 - a[i].S.F * m));
        update2(a[i].S.F, max(t6, t4));
    }
    printf("%lld\n", max(query1(k, base - 1) + k * m, query2(0, k)));
    return 0;
}

Compilation message

salesman.cpp: In function 'int main()':
salesman.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     scanf("%lld%lld%lld%lld", &n, &m1, &m2, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         scanf("%lld%lld%lld", &a[i].F, &a[i].S.F, &a[i].S.S);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
62.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 16684 KB Output is correct
2 Correct 9 ms 16676 KB Output is correct
3 Correct 9 ms 16720 KB Output is correct
4 Correct 9 ms 16800 KB Output is correct
5 Correct 10 ms 16840 KB Output is correct
6 Correct 31 ms 17540 KB Output is correct
7 Correct 48 ms 18736 KB Output is correct
8 Correct 89 ms 20848 KB Output is correct
9 Correct 123 ms 22600 KB Output is correct
10 Correct 214 ms 28456 KB Output is correct
11 Correct 266 ms 29120 KB Output is correct
12 Correct 338 ms 32212 KB Output is correct
13 Correct 332 ms 32456 KB Output is correct
14 Correct 417 ms 37348 KB Output is correct
15 Correct 338 ms 36364 KB Output is correct
16 Correct 409 ms 36524 KB Output is correct
17 Correct 7 ms 16720 KB Output is correct
18 Incorrect 7 ms 16744 KB Output isn't correct
19 Incorrect 8 ms 16720 KB Output isn't correct
20 Incorrect 8 ms 16720 KB Output isn't correct
21 Incorrect 9 ms 16720 KB Output isn't correct
22 Incorrect 9 ms 16848 KB Output isn't correct
23 Incorrect 10 ms 16848 KB Output isn't correct
24 Incorrect 10 ms 16848 KB Output isn't correct
25 Incorrect 76 ms 20404 KB Output isn't correct
26 Incorrect 144 ms 24136 KB Output isn't correct
27 Incorrect 269 ms 29388 KB Output isn't correct
28 Incorrect 290 ms 30272 KB Output isn't correct
29 Incorrect 339 ms 35096 KB Output isn't correct
30 Incorrect 374 ms 35848 KB Output isn't correct