Submission #68031

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
68031	2018-08-15 19:32:38	KLPP	Ancient Books (IOI17_books)	C++14	70 / 100	2053 ms	104732 KiB

books

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "books.h"
#include<iostream>
#include<vector>
#include<queue>
#include<map>
using namespace std;
typedef long long lld;
typedef pair<int,int> state;
typedef std::map<state,lld>::iterator mi;
int arr[1000000];
int n;
int maxa,maxb;
map<state,lld>DP;
lld computevalue(int i, int j){
  //cout<<i<<" "<<j<<endl;
  if(i<=maxa && maxb<=j)return 0;
  mi it=DP.find(state(i,j));
  if(it!=DP.end())return it->second;
  int start=i;
  int end=j;
  int ps=start;
  int pe=end;
  while(pe<=end){
    while(ps>=start){
      start=min(start,arr[ps]);
      end=max(end,arr[ps]);
      ps--;
    }
    start=min(start,arr[pe]);
    end=max(end,arr[pe]);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 28 / 28
• Subtask 4: 20 / 20
• Subtask 5: 0 / 30