Submission #45406059

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--){
       long long n, m;
       cin >> n >> m;
       long long a[n];
       long long b[n];
       for(int i = 0; i < n; i++){
           cin >> a[i];
           b[i] = a[i];
       }
       sort(b, b + n);
       long long line = n / m + (n % m != 0);
       long long w = 0;
       for(int i = n - 1; i >= n - line; i--){
           w += (long long)b[i] + 1;
       }
       long long l = 1;
       long long r = w;
       while(l <= r){
           bool flag = true;
           long long mid = l + (r - l) / 2;
           //long long mid = (long long)10000000008;
           long long cur_sum = 0;
           int cur_line = m;
           for(int i = 0; i < n; i++){
               if(cur_sum == 0 && cur_sum + a[i] <= mid){
                   cur_sum += a[i];
               }
               else if(cur_sum + 1 + a[i] <= mid){
                   cur_sum += a[i] + 1;
               }
               else{
                   cur_line--;
                   if(cur_sum == 0 || cur_line == 0){
                       flag = false;
                       break;
                   }
                   cur_sum = a[i];
               }
           }
           if(flag == true){
               w = mid;
               r = mid - 1;
           }
           else{
               l = mid + 1;
           }
       }
       cout << w;

    }
    return 0;
}

Submission Info

Submission Time
Task D - Minimum Width
User LetsHaveFun2
Language C++ 20 (gcc 12.2)
Score 0
Code Size 1560 Byte
Status WA
Exec Time 47 ms
Memory 6688 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
AC × 3
AC × 15
WA × 10
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_random_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, 02_handmade_19.txt, 02_handmade_20.txt, 02_handmade_21.txt, 02_handmade_22.txt, 02_handmade_23.txt, 02_handmade_24.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 1 ms 3496 KiB
00_sample_01.txt AC 1 ms 3624 KiB
00_sample_02.txt AC 1 ms 3564 KiB
01_random_03.txt AC 47 ms 6532 KiB
01_random_04.txt WA 32 ms 6588 KiB
01_random_05.txt AC 45 ms 6624 KiB
01_random_06.txt AC 43 ms 6528 KiB
01_random_07.txt AC 22 ms 5036 KiB
01_random_08.txt WA 15 ms 4400 KiB
01_random_09.txt WA 15 ms 4732 KiB
01_random_10.txt AC 44 ms 6404 KiB
01_random_11.txt WA 23 ms 5820 KiB
01_random_12.txt WA 15 ms 5008 KiB
01_random_13.txt WA 11 ms 4448 KiB
01_random_14.txt WA 18 ms 5380 KiB
01_random_15.txt AC 6 ms 4164 KiB
01_random_16.txt AC 29 ms 6176 KiB
01_random_17.txt AC 14 ms 4900 KiB
01_random_18.txt AC 6 ms 4076 KiB
02_handmade_19.txt AC 23 ms 6688 KiB
02_handmade_20.txt AC 10 ms 6688 KiB
02_handmade_21.txt WA 15 ms 6604 KiB
02_handmade_22.txt WA 21 ms 6620 KiB
02_handmade_23.txt AC 14 ms 6632 KiB
02_handmade_24.txt WA 17 ms 6688 KiB