(cache)Submission #63285964 - AtCoder Beginner Contest 395

Contest Duration: 2025-03-01(Sat) 21:00 - 2025-03-01(Sat) 22:40 (local time) (100 minutes) Back to Home

Submission #63285964

Source Code Expand

Copy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Not written by the author
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int N;
    ll X;
    cin >> N >> X;
    vector<ll> U(N), D(N);
    vector<ll> sumUD(N);
    for (int i = 0; i < N; i++){
        cin >> U[i] >> D[i];
        sumUD[i] = U[i] + D[i];
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

// Not written by the author

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int N;
    ll X;
    cin >> N >> X;
    vector<ll> U(N), D(N);
    vector<ll> sumUD(N);
    for (int i = 0; i < N; i++){
        cin >> U[i] >> D[i];
        sumUD[i] = U[i] + D[i];
    }
 
    ll Hmax = *min_element(sumUD.begin(), sumUD.end());
 
   auto feasible = [&](ll H) -> bool {
        ll L = max(0LL, H - D[0]);
        ll R = min(U[0], H);
        if(L > R) return false;
        for (int i = 1; i < N; i++){
            ll curL = max( max(0LL, H - D[i]), L - X );
            ll curR = min( min(U[i], H), R + X );
            if(curL > curR) return false;
            L = curL;
            R = curR;
        }
        return true;
    };
 
   ll lo = 0, hi = Hmax;
    while(lo < hi){
        ll mid = (lo + hi + 1) / 2;
        if(feasible(mid))
            lo = mid;
        else
            hi = mid - 1;
    }
    ll bestH = lo;
 
    ll totalSum = 0;
    for (int i = 0; i < N; i++){
        totalSum += (U[i] + D[i]);
    }
    ll ans = totalSum - (ll)N * bestH;
    cout << ans << "\n";
    return 0;
}

Submission Info

Submission Time	2025-03-01 21:57:53
Task	F - Smooth Occlusion
User	VIP1109
Language	C++ 20 (gcc 12.2)
Score	500
Code Size	1285 Byte
Status	AC
Exec Time	35 ms
Memory	7868 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

500 / 500

Status

× 4

× 69

Set Name	Test Cases
Sample	00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt
All	00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 01_random_21.txt, 01_random_22.txt, 01_random_23.txt, 01_random_24.txt, 01_random_25.txt, 01_random_26.txt, 01_random_27.txt, 01_random_28.txt, 01_random_29.txt, 01_random_30.txt, 01_random_31.txt, 01_random_32.txt, 01_random_33.txt, 01_random_34.txt, 01_random_35.txt, 01_random_36.txt, 01_random_37.txt, 01_random_38.txt, 01_random_39.txt, 01_random_40.txt, 01_random_41.txt, 01_random_42.txt, 01_random_43.txt, 01_random_44.txt, 01_random_45.txt, 01_random_46.txt, 01_random_47.txt, 01_random_48.txt, 01_random_49.txt, 01_random_50.txt, 01_random_51.txt, 01_random_52.txt, 01_random_53.txt, 01_random_54.txt, 01_random_55.txt, 01_random_56.txt, 01_random_57.txt, 01_random_58.txt, 01_random_59.txt, 01_random_60.txt, 01_random_61.txt, 01_random_62.txt, 01_random_63.txt, 01_random_64.txt, 01_random_65.txt, 01_random_66.txt, 01_random_67.txt, 01_random_68.txt

Case Name	Status	Exec Time	Memory
00_sample_00.txt	AC	1 ms	3448 KiB
00_sample_01.txt	AC	1 ms	3416 KiB
00_sample_02.txt	AC	1 ms	3388 KiB
00_sample_03.txt	AC	1 ms	3424 KiB
01_random_04.txt	AC	27 ms	7736 KiB
01_random_05.txt	AC	28 ms	7812 KiB
01_random_06.txt	AC	27 ms	7772 KiB
01_random_07.txt	AC	27 ms	7736 KiB
01_random_08.txt	AC	27 ms	7780 KiB
01_random_09.txt	AC	29 ms	7736 KiB
01_random_10.txt	AC	27 ms	7800 KiB
01_random_11.txt	AC	28 ms	7748 KiB
01_random_12.txt	AC	28 ms	7812 KiB
01_random_13.txt	AC	28 ms	7740 KiB
01_random_14.txt	AC	28 ms	7744 KiB
01_random_15.txt	AC	29 ms	7740 KiB
01_random_16.txt	AC	29 ms	7744 KiB
01_random_17.txt	AC	28 ms	7728 KiB
01_random_18.txt	AC	29 ms	7804 KiB
01_random_19.txt	AC	27 ms	7732 KiB
01_random_20.txt	AC	27 ms	7772 KiB
01_random_21.txt	AC	29 ms	7780 KiB
01_random_22.txt	AC	27 ms	7804 KiB
01_random_23.txt	AC	28 ms	7804 KiB
01_random_24.txt	AC	29 ms	7804 KiB
01_random_25.txt	AC	29 ms	7864 KiB
01_random_26.txt	AC	28 ms	7712 KiB
01_random_27.txt	AC	30 ms	7812 KiB
01_random_28.txt	AC	27 ms	7812 KiB
01_random_29.txt	AC	28 ms	7864 KiB
01_random_30.txt	AC	26 ms	7772 KiB
01_random_31.txt	AC	28 ms	7780 KiB
01_random_32.txt	AC	27 ms	7800 KiB
01_random_33.txt	AC	30 ms	7812 KiB
01_random_34.txt	AC	25 ms	7208 KiB
01_random_35.txt	AC	25 ms	7224 KiB
01_random_36.txt	AC	9 ms	4312 KiB
01_random_37.txt	AC	3 ms	3540 KiB
01_random_38.txt	AC	14 ms	5356 KiB
01_random_39.txt	AC	23 ms	6944 KiB
01_random_40.txt	AC	6 ms	3904 KiB
01_random_41.txt	AC	13 ms	4840 KiB
01_random_42.txt	AC	16 ms	5688 KiB
01_random_43.txt	AC	15 ms	5356 KiB
01_random_44.txt	AC	22 ms	6412 KiB
01_random_45.txt	AC	11 ms	4568 KiB
01_random_46.txt	AC	33 ms	7816 KiB
01_random_47.txt	AC	32 ms	7788 KiB
01_random_48.txt	AC	35 ms	7868 KiB
01_random_49.txt	AC	26 ms	7780 KiB
01_random_50.txt	AC	33 ms	7724 KiB
01_random_51.txt	AC	28 ms	7748 KiB
01_random_52.txt	AC	27 ms	7740 KiB
01_random_53.txt	AC	30 ms	7808 KiB
01_random_54.txt	AC	27 ms	7792 KiB
01_random_55.txt	AC	26 ms	7744 KiB
01_random_56.txt	AC	26 ms	7744 KiB
01_random_57.txt	AC	28 ms	7804 KiB
01_random_58.txt	AC	26 ms	7772 KiB
01_random_59.txt	AC	27 ms	7704 KiB
01_random_60.txt	AC	28 ms	7732 KiB
01_random_61.txt	AC	27 ms	7740 KiB
01_random_62.txt	AC	29 ms	7640 KiB
01_random_63.txt	AC	34 ms	7728 KiB
01_random_64.txt	AC	32 ms	7724 KiB
01_random_65.txt	AC	32 ms	7732 KiB
01_random_66.txt	AC	33 ms	7772 KiB
01_random_67.txt	AC	1 ms	3464 KiB
01_random_68.txt	AC	1 ms	3432 KiB