dwangoプログラミングコンテスト

Submission #8194115

Source codeソースコード

// ※※※ 解答不能 ※※※
// square1001氏.
// https://atcoder.jp/contests/dwango2015-prelims/submissions/2072172
#include <bits/stdc++.h>
using namespace std;
int N, L, p[200009], a, b; long long s[200009];
int main() {
    scanf("%d %d", &N, &L);
    for(int i = 0; i < N; i++){
        scanf("%d %d %d", &p[i], &a, &b);
        s[i + 1] = s[i] + a - b;
    }
    p[N] = p[0] + L;
    for(int i = N + 1; i <= 2 * N; i++) p[i] = p[i - N] + L, s[i] = s[i - N];
    long long l = -1LL << 40, r = 1LL << 40;
    while(r - l > 1){
        long long m = (l + r) >> 1;
        int cnt = 0;
        for(int i = 1; i <= N; i++) if(s[i] < m) cnt += p[i] - p[i - 1];
        if(2 * cnt < L) l = m;
        else            r = m;
    }
    int pos = -1;
    for(int i = 0; i < N; i++) if(s[i] == l) pos = i;
    assert(pos != -1);
    long long ret = 0;
    for(int i = pos; i < N + pos; i++){
        if(s[i] == s[i + 1]) continue;
        if(s[i] < s[i + 1]){
            if(s[i] <= l && l <= s[i + 1]){
                ret += max(l - s[i], 0LL) * p[i];
                ret -= max(s[i + 1] - l, 0LL) * p[i];
            }else{
                ret += (s[i + 1] - s[i]) * p[i] * (s[i] > l ? -1 : 1);
            }
        }else{
            if(s[i + 1] <= l && l <= s[i]){
                ret += max(s[i] - l, 0LL) * p[i];
                ret -= max(l - s[i + 1], 0LL) * p[i];
            }else{
                ret += (s[i] - s[i + 1]) * p[i] * (s[i] > l ? 1 : -1);
            }
        }
    }
    printf("%lld\n", ret);
    return 0;
}

Submission

Task問題 D - タクシー
User nameユーザ名 at_abcde
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 1585 Byte
File nameファイル名
Exec time実行時間 30 ms
Memory usageメモリ使用量 2560 KB

Compiler messageコンパイルメッセージ

./Main.cpp: In function ‘int main()’:
./Main.cpp:8:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &N, &L);
^
./Main.cpp:10:41: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &p[i], &a, &b);
^

Test case

Set

Set name Score得点 / Max score Cases
Sample - subtask0-sample-01.txt,subtask0-sample-02.txt
Subtask1 15 / 15 subtask0-sample-01.txt,subtask0-sample-02.txt,subtask1-01.txt,subtask1-02.txt,subtask1-03.txt,subtask1-04.txt,subtask1-05.txt,subtask1-06.txt,subtask1-07.txt,subtask1-08.txt,subtask1-09.txt,subtask1-10.txt,subtask1-11.txt,subtask1-12.txt,subtask1-13.txt,subtask1-14.txt,subtask1-15.txt,subtask1-16.txt,subtask1-17.txt,subtask1-18.txt,subtask1-19.txt,subtask1-20.txt
Subtask2 30 / 30 subtask0-sample-01.txt,subtask0-sample-02.txt,subtask1-01.txt,subtask1-02.txt,subtask1-03.txt,subtask1-04.txt,subtask1-05.txt,subtask1-06.txt,subtask1-07.txt,subtask1-08.txt,subtask1-09.txt,subtask1-10.txt,subtask1-11.txt,subtask1-12.txt,subtask1-13.txt,subtask1-14.txt,subtask1-15.txt,subtask1-16.txt,subtask1-17.txt,subtask1-18.txt,subtask1-19.txt,subtask1-20.txt,subtask2-01.txt,subtask2-02.txt,subtask2-03.txt,subtask2-04.txt,subtask2-05.txt,subtask2-06.txt,subtask2-07.txt,subtask2-08.txt,subtask2-09.txt,subtask2-10.txt,subtask2-11.txt,subtask2-12.txt,subtask2-13.txt,subtask2-14.txt,subtask2-15.txt,subtask2-16.txt,subtask2-17.txt,subtask2-18.txt,subtask2-19.txt,subtask2-20.txt
Subtask3 55 / 55 subtask0-sample-01.txt,subtask0-sample-02.txt,subtask1-01.txt,subtask1-02.txt,subtask1-03.txt,subtask1-04.txt,subtask1-05.txt,subtask1-06.txt,subtask1-07.txt,subtask1-08.txt,subtask1-09.txt,subtask1-10.txt,subtask1-11.txt,subtask1-12.txt,subtask1-13.txt,subtask1-14.txt,subtask1-15.txt,subtask1-16.txt,subtask1-17.txt,subtask1-18.txt,subtask1-19.txt,subtask1-20.txt,subtask2-01.txt,subtask2-02.txt,subtask2-03.txt,subtask2-04.txt,subtask2-05.txt,subtask2-06.txt,subtask2-07.txt,subtask2-08.txt,subtask2-09.txt,subtask2-10.txt,subtask2-11.txt,subtask2-12.txt,subtask2-13.txt,subtask2-14.txt,subtask2-15.txt,subtask2-16.txt,subtask2-17.txt,subtask2-18.txt,subtask2-19.txt,subtask2-20.txt,subtask3-01.txt,subtask3-02.txt,subtask3-03.txt,subtask3-04.txt,subtask3-05.txt,subtask3-06.txt,subtask3-07.txt,subtask3-08.txt,subtask3-09.txt,subtask3-10.txt,subtask3-11.txt,subtask3-12.txt,subtask3-13.txt,subtask3-14.txt,subtask3-15.txt,subtask3-16.txt,subtask3-17.txt,subtask3-18.txt,subtask3-19.txt,subtask3-20.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask0-sample-01.txt AC 1 ms 256 KB
subtask0-sample-02.txt AC 1 ms 256 KB
subtask1-01.txt AC 1 ms 256 KB
subtask1-02.txt AC 1 ms 256 KB
subtask1-03.txt AC 2 ms 384 KB
subtask1-04.txt AC 2 ms 384 KB
subtask1-05.txt AC 2 ms 384 KB
subtask1-06.txt AC 2 ms 384 KB
subtask1-07.txt AC 2 ms 384 KB
subtask1-08.txt AC 2 ms 384 KB
subtask1-09.txt AC 2 ms 384 KB
subtask1-10.txt AC 2 ms 384 KB
subtask1-11.txt AC 2 ms 384 KB
subtask1-12.txt AC 2 ms 384 KB
subtask1-13.txt AC 2 ms 384 KB
subtask1-14.txt AC 2 ms 384 KB
subtask1-15.txt AC 2 ms 384 KB
subtask1-16.txt AC 2 ms 384 KB
subtask1-17.txt AC 2 ms 384 KB
subtask1-18.txt AC 2 ms 384 KB
subtask1-19.txt AC 2 ms 384 KB
subtask1-20.txt AC 2 ms 384 KB
subtask2-01.txt AC 3 ms 384 KB
subtask2-02.txt AC 3 ms 384 KB
subtask2-03.txt AC 2 ms 384 KB
subtask2-04.txt AC 3 ms 384 KB
subtask2-05.txt AC 2 ms 384 KB
subtask2-06.txt AC 2 ms 384 KB
subtask2-07.txt AC 3 ms 384 KB
subtask2-08.txt AC 3 ms 384 KB
subtask2-09.txt AC 3 ms 384 KB
subtask2-10.txt AC 3 ms 384 KB
subtask2-11.txt AC 3 ms 384 KB
subtask2-12.txt AC 3 ms 384 KB
subtask2-13.txt AC 3 ms 384 KB
subtask2-14.txt AC 2 ms 384 KB
subtask2-15.txt AC 3 ms 384 KB
subtask2-16.txt AC 3 ms 384 KB
subtask2-17.txt AC 3 ms 384 KB
subtask2-18.txt AC 2 ms 384 KB
subtask2-19.txt AC 2 ms 384 KB
subtask2-20.txt AC 2 ms 384 KB
subtask3-01.txt AC 7 ms 768 KB
subtask3-02.txt AC 16 ms 1408 KB
subtask3-03.txt AC 30 ms 2560 KB
subtask3-04.txt AC 27 ms 2560 KB
subtask3-05.txt AC 30 ms 2560 KB
subtask3-06.txt AC 30 ms 2560 KB
subtask3-07.txt AC 30 ms 2560 KB
subtask3-08.txt AC 30 ms 2560 KB
subtask3-09.txt AC 26 ms 2560 KB
subtask3-10.txt AC 30 ms 2560 KB
subtask3-11.txt AC 25 ms 2560 KB
subtask3-12.txt AC 30 ms 2560 KB
subtask3-13.txt AC 30 ms 2560 KB
subtask3-14.txt AC 30 ms 2560 KB
subtask3-15.txt AC 30 ms 2560 KB
subtask3-16.txt AC 30 ms 2560 KB
subtask3-17.txt AC 30 ms 2560 KB
subtask3-18.txt AC 29 ms 2560 KB
subtask3-19.txt AC 30 ms 2560 KB
subtask3-20.txt AC 30 ms 2560 KB