Submission #33472


Source Code Expand

Copy
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <iostream>
#include <cmath>
#include <algorithm>

#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <map>

using namespace std;

typedef long long ll;

#define M 100

int n;
int w[M];
int t[M][M];
int h[M];

bool ok(int a){
  memset(t, 0, sizeof(t)); memset(h, 0, sizeof(h));
  for(int i = 0; i < n; i++){
    int cand = -1;
    for(int j = 0; j < a; j++){
      if(h[j] == 0){
        if(cand < 0)cand = j;
      }else{
        if(cand < 0){
          if(t[j][h[j]-1] >= w[i])cand = j;
        }else{
          if(t[j][h[j]-1] >= w[i] && t[j][h[j]-1] < t[cand][h[cand]-1])
            cand = j;
        }
      }
    }
    if(cand < 0)return false;
    t[cand][h[cand]++] = w[i];
  }
  return ok;
}

int main(){
  //cin.tie(0);
  //ios_base::sync_with_stdio(false);

  scanf("%d", &n);
  for(int i = 0; i < n; i++)
    scanf("%d", w+i);
  int left = 1, right = n;
  int ans = n;
  while(left <= right){
    int m = (left+right)/2;
    if(ok(m)){
      right = m-1;
      ans = min(ans, m);
    }else{
      left = m+1;
    }
  }
  printf("%d\n", ans);

  return 0;
}

Submission Info

Submission Time
Task C - 積み重ね
User chronotable
Language C++ (G++ 4.6.4)
Score 100
Code Size 1251 Byte
Status AC
Exec Time 22 ms
Memory 820 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:53:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:55:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 44
Set Name Test Cases
All 00_min.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 00_sample_05.txt, 01_rnd_00.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 02_maxrnd_00.txt, 02_maxrnd_01.txt, 02_maxrnd_02.txt, 02_maxrnd_03.txt, 02_maxrnd_04.txt, 02_maxrnd_05.txt, 02_maxrnd_06.txt, 02_maxrnd_07.txt, 02_maxrnd_08.txt, 02_maxrnd_09.txt, 02_maxrnd_10.txt, 02_maxrnd_11.txt, 02_maxrnd_12.txt, 02_maxrnd_13.txt, 02_maxrnd_14.txt, 02_maxrnd_15.txt, 02_maxrnd_16.txt, 02_maxrnd_17.txt, 02_maxrnd_18.txt, 02_maxrnd_19.txt, 03_increase_00.txt, 03_increase_01.txt, 03_increase_02.txt, 04_decrease_00.txt, 04_decrease_01.txt, 04_decrease_02.txt, 05_same_00.txt, 05_same_01.txt
Case Name Status Exec Time Memory
00_min.txt AC 22 ms 784 KB
00_sample_01.txt AC 22 ms 772 KB
00_sample_02.txt AC 20 ms 788 KB
00_sample_03.txt AC 21 ms 764 KB
00_sample_04.txt AC 20 ms 788 KB
00_sample_05.txt AC 21 ms 760 KB
01_rnd_00.txt AC 21 ms 820 KB
01_rnd_01.txt AC 21 ms 788 KB
01_rnd_02.txt AC 20 ms 792 KB
01_rnd_03.txt AC 20 ms 784 KB
01_rnd_04.txt AC 20 ms 784 KB
01_rnd_05.txt AC 21 ms 788 KB
01_rnd_06.txt AC 21 ms 820 KB
01_rnd_07.txt AC 21 ms 764 KB
01_rnd_08.txt AC 21 ms 784 KB
01_rnd_09.txt AC 22 ms 792 KB
02_maxrnd_00.txt AC 21 ms 788 KB
02_maxrnd_01.txt AC 21 ms 732 KB
02_maxrnd_02.txt AC 21 ms 764 KB
02_maxrnd_03.txt AC 20 ms 788 KB
02_maxrnd_04.txt AC 22 ms 780 KB
02_maxrnd_05.txt AC 21 ms 816 KB
02_maxrnd_06.txt AC 21 ms 764 KB
02_maxrnd_07.txt AC 21 ms 784 KB
02_maxrnd_08.txt AC 22 ms 780 KB
02_maxrnd_09.txt AC 21 ms 732 KB
02_maxrnd_10.txt AC 21 ms 776 KB
02_maxrnd_11.txt AC 22 ms 820 KB
02_maxrnd_12.txt AC 20 ms 784 KB
02_maxrnd_13.txt AC 22 ms 764 KB
02_maxrnd_14.txt AC 22 ms 796 KB
02_maxrnd_15.txt AC 20 ms 788 KB
02_maxrnd_16.txt AC 22 ms 760 KB
02_maxrnd_17.txt AC 22 ms 784 KB
02_maxrnd_18.txt AC 21 ms 792 KB
02_maxrnd_19.txt AC 21 ms 788 KB
03_increase_00.txt AC 20 ms 784 KB
03_increase_01.txt AC 20 ms 780 KB
03_increase_02.txt AC 21 ms 792 KB
04_decrease_00.txt AC 21 ms 796 KB
04_decrease_01.txt AC 21 ms 788 KB
04_decrease_02.txt AC 20 ms 792 KB
05_same_00.txt AC 21 ms 764 KB
05_same_01.txt AC 22 ms 744 KB