akhauriyash/Code-Regression huggingface dataset:
const fi='agc017_a.inp';
        fo='agc017_a.out';
type hanh=extended;
var d:array[0..50] of hanh;
        a,b,p:longint;
procedure mori;
        var i:longint;
        begin
                d[0]:=1;
                for i:=1 to 50 do d[i]:=d[i-1]*i;
        end;
procedure ran;
        var n,x,i:longint;
        begin
                readln(n,p);
                a:=0;
                b:=0;
                p:=p mod 2;
                for i:=1 to n do
                        begin
                                read(x);
                                if x mod 2=0 then inc(a) else inc(b);
                        end;
        end;
function conan:hanh;
        var     i:longint;
                aa,bb:hanh;
        begin
               bb:=1;
                        for i:=1 to b do
                                if i mod 2=0 then
                                        bb:=bb+d[b]/(d[i]*d[b-i]);
               aa:=1;
                        for i:=1 to a do
                                aa:=aa+d[a]/(d[i]*d[a-i]);
              exit(aa*bb);

        end;
function conan1:hanh;
        var aa,bb:hanh;
                i:longint;
        begin
                bb:=0;
                        for i:=1 to b do
                                if i mod 2=1 then
                                        bb:=bb+d[b]/(d[i]*d[b-i]);
                aa:=1;
                        for i:=1 to a do
                                aa:=aa+d[a]/(d[i]*d[a-i]);
                exit(aa*bb);
        end;
begin

        ran;
        mori;
        if p=0 then writeln(conan:0:0) else writeln(conan1:0:0);
end.


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef double DB;

#define F(i,a,b) for(int i=(a);i<=(b);++i)
#define R(i,n) for(int i=0;i<(n);++i)
#define fill(a,b) memset(a,b,sizeof a)

const int maxn = 1e5 + 10;
int ball[maxn],yes[maxn],x[maxn],y[maxn];
int n,m;

int main()
{
	//freopen("test.txt","r",stdin);
	cin >> n >> m;
	R(i,m) scanf("%d%d",x+i,y+i);
	F(i,1,n) ball[i] = 1;
	yes[1] = 1;
	R(i,m)
	{
		if(yes[x[i]]) yes[y[i]] = 1;
		ball[x[i]]--;
		ball[y[i]]++;
		if(ball[x[i]] == 0) yes[x[i]] = 0;
	}
	int cnt = 0;
	F(i,1,n) if(yes[i] && ball[i]) ++cnt;
	printf("%d\n",cnt);
	return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
using namespace std;
typedef long long int ll;

// clang-format off
#ifdef _DEBUG_
#define dump(...) do{ cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; PPPPP(__VA_ARGS__); cerr << endl; } while(false)
template<typename T> void PPPPP(T t) { cerr << t; }
template<typename T, typename... S> void PPPPP(T t, S... s) { cerr << t << ", "; PPPPP(s...); }
#else
#define dump(...)
#endif
template<typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template<typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }
template<typename T>
bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false;}
template<typename T>
bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false;}
// clang-format on

#include <functional>
#include <utility>
using P = pair<int, int>;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<vector<P>> G(n);
    int k = 0;
    REP(i, 0, n - 1) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        G[a].emplace_back(b, i);
        G[b].emplace_back(a, i);
        chmax(k, (int)G[a].size());
        chmax(k, (int)G[b].size());
    }
    cout << k << endl;
    vector<int> color(n - 1, -1);
    function<void(int, int, int)> rec = [&](int prev, int pos, int c) {
        int x = 1;
        for (auto &vvv : G[pos]) {
            int id = vvv.second;
            int v = vvv.first;
            if (v == prev) continue;
            if (c == x) {
                x++;
            }
            color[id] = x;
            rec(pos, v, x);
            x++;
        }
    };
    rec(-1, 0, -1);
    REP(i, 0, n - 1) {
        cout << color[i] << endl;
    }

    return 0;
}


Measured memory_bytes: 9216
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <numeric>

using namespace std;
char c[110][110];
int main(){
    string s;
    cin>>s;
    for(int i=s.size()-1;i>=0;i--){
        if(s[i]=='m'){
            if(i<4){
                cout<<"NO"<<endl;
                return 0;
            }
            if(s.substr(i-4,4)=="drea")i-=4;
            else {
                cout<<"NO"<<endl;
                return 0;
            }
            continue;
        }
        if(s[i]=='e'){
            if(i<4){
                cout<<"NO"<<endl;
                return 0;
            }
            if(s.substr(i-4,4)=="eras")i-=4;
            else {
                cout<<"NO"<<endl;
                return 0;
            }
            continue;
        }
        if(s[i]=='r'){
            if(i>=6 && s.substr(i-6,6)=="dreame")i-=6;
            else if(i>=5 && s.substr(i-5,5)=="erase")i-=5;
            else {
                cout<<"NO"<<endl;
                return 0;
            }
            continue;
        }
    }
    cout<<"YES"<<endl;
    
}

   


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define pi 3.14159265358979323846

int main(){
	double a,b,h,m;
	cin >> a >> b >> h >> m;
	double deg;
	if(m!=0) deg=abs(((30*h)+(30*(m/60)))-(30*m/5));
	else deg=abs((30*h)-(6*m));
	//cout << deg << "\n";
	double ans=(a*a)+(b*b)-(2*a*b*cos(deg*pi/180));
	ans=sqrt(ans);
	cout << fixed;
	cout << setprecision(20);
	cout << ans << "\n";
}

Measured memory_bytes: 4224
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main() {
	int  a[100000], i, cnt = 0,  k = 0,x[100000];
        unsigned long int n,sum=1;
	scanf("%lu", &n);
	for (i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
       for(i=0;i<100000;i++){
              x[i]=0;
       }
	for (i = 0; i < n; i++) {
             x[a[i]]+=1;
             if (x[a[i]]>2&&a[i]!=0||x[a[i]]>1&&a[i]==0) {
			printf("0");
			k = 1;
			break;
	       }
       }
 
	if (k == 0) {
		for (i = 0; i < n / 2; i++) {
					sum *= 2;
                                        if (sum >= 1000000007) {
				           sum -= 1000000007;
			}

		}
		printf("%lu\n", sum);
                return 0;
	}
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (int i = j; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
//name[i][j]-> vvl name(i,vl(j))
//map<int,int>mp
//余りを切り上げる =>  (a + b - 1) / b 

signed main(){
	int a,b; cin>>a>>b;
	bool ok=false;
	rep(i,0,a+1){
		int j=a-i;
		if(i*2+j*4==b) ok=true;
	}
	if(ok) cout<<"Yes";
	else cout<<"No";
	
	return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;

int selectionSort(int A[], int N) {
    int sw = 0, temp;

    for (int i = 0; i < N; i++) {
        int minj = i;
        for (int j = i+1; j < N; j++) {
            if (A[minj] > A[j]) {
                minj = j;
            }
        }

        if (i != minj) {
            sw++;
            temp = A[minj];
            A[minj] = A[i];
            A[i] = temp;
        }

    }

    return sw;   
}

int main(int argc, char const *argv[]) {
    int N;
    cin >> N;
    int A[N];
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    
    int sw = selectionSort(A, N);
    for (int i = 0; i < N-1; i++) {
        cout << A[i] << ' ';
    }
    cout << A[N-1] << endl;
    cout << sw << endl;

    return 0;
}



Measured memory_bytes: 3088
s = input()

def run_length_compress(string):
    """文字列をランレングス圧縮する
    例) string = "aabccaaabb" -> [(2, a), (1, b), (2, c), (3, a), (2, b)]
    """
    string = string + "@" # string中に絶対に現れない文字を番兵とする
    n = len(string)

    begin = 0
    end = 1
    cnt = 1
    ans = []
    while True:
        if end >= n:
            break
        if string[begin] == string[end]:
            end += 1
            cnt += 1
        else:
            ans.append((cnt, string[begin]))
            begin = end
            end = begin + 1
            cnt = 1

    return ans
  
print(len(run_length_compress(s)) - 1)

Measured memory_bytes: 45680
#include<bits/stdc++.h>
using namespace std;

int main(){
    int h, w;
    cin >> h >> w;
    char x;
    vector<vector<bool>> grid(h, vector<bool>(w, true));
    for (int i = 0; i < h; i++){
        for (int j = 0; j < w; j++){
            cin >> x;
            if (x == '#') grid[i][j] = false;
        }
    }

    vector<vector<int>> up(h, vector<int>(w, 0));
    vector<vector<int>> down(h, vector<int>(w, 0));
    vector<vector<int>> right(h, vector<int>(w, 0));
    vector<vector<int>> left(h, vector<int>(w, 0));

    for (int i = 0; i < h; i++){
        for (int j = 0; j < w; j++){
            if (grid[i][j] == true){
                if (j == 0) left[i][j] = 1;
                else left[i][j] = left[i][j-1] + 1;
            }
        }
    }
    for (int i = 0; i < h; i++){
        for (int j = w - 1; j >= 0; j--){
            if (grid[i][j] == true){
                if (j == w - 1) right[i][j] = 1;
                else right[i][j] = right[i][j+1] + 1;
            }
        }
    }
    for (int i = 0; i < w; i++){
        for (int j = 0; j < h; j++){
            if (grid[j][i] == true){
                if (j == 0) up[j][i] = 1;
                else up[j][i] = up[j-1][i] + 1;
            }
        }
    }
    for (int i = 0; i < w; i++){
        for (int j = h - 1; j >= 0; j--){
            if (grid[j][i] == true){
                if (j == h - 1) down[j][i] = 1;
                else down[j][i] = down[j+1][i] + 1;
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < h; i++){
        for (int j = 0; j < w; j++){
            if (grid[i][j]){
                ans = max({ans, up[i][j] + down[i][j] + left[i][j] + right[i][j] - 3});
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 63616
<?php
fscanf(STDIN,"%d",$n);
 
$re = array();
$zero_flag = true;
for($i=0;$i<$n;$i++){
    fscanf(STDIN,"%d",$s);
    $s_li[] = $s;
    if($s%10!=0){
      $zero_flag = false;
    }
 }

if($zero_flag){
  echo "0\n";
  exit;
}

sort($s_li);
$sum = array_sum($s_li);
$i=0;
$sum_re = $sum;
while($sum_re%10==0){
  $sum_re = $sum;
  $sum_re -= $s_li[$i];
  $i++;
}
//print_r($s_li);


echo $sum_re."\n";

 

Measured memory_bytes: 4604
#include <stdio.h>
int main(void){
	int a,b,c;
	scanf("%d %d %d",&a,&b,&c);
	if(a<=b&&a<=c){
		if(b<=c){
			printf("%d %d %d\n",a,b,c);
		}else{
			printf("%d %d %d\n",a,c,b);
		}
	}else if(b<=c&&b<=a){
		if(a<=c){
			printf("%d %d %d\n",b,a,c);
		}else{
			printf("%d %d %d\n",b,c,a);
		}
	}else if(c<=b&&c<=a){
		if(a<=b){
			printf("%d %d %d\n",c,a,b);
		}else{
			printf("%d %d %d\n",c,b,a);
		}
	}
    return 0;
}


Measured memory_bytes: 2040
#include<bits/stdc++.h>
using namespace std;
int main(){
    char B;
    scanf("%c", &B);
    switch(B){
        case 'A': printf("T"); break;
        case 'G': printf("C"); break;
        case 'T': printf("A"); break;
        case 'C': printf("G"); break;
    }
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define let const auto
#define rep(i,n) for(int i=0; i<(n); ++i)
#define reps(i,f,n) for(int i=(f); i<=(n); ++i)
#define outl(x) cout<< (x) << '\n'

char mas[102][102];

int main()
{
   cin.tie(0), ios::sync_with_stdio(false);
   constexpr int H = 60;
   constexpr int W = 80;
   int w, b;
   cin >> w >> b;

   cout << H << ' ' << W << '\n';

   for (int i=0; i<H/2; ++i)
      for (int j=0; j<W; ++j)
         mas[i][j] = '.';

   for (int i=H/2; i<H; ++i)
      for (int j=0; j<W; ++j)
         mas[i][j] = '#';

   for (int i=0; i<H/2; i+=2) {
      for (int j=0; j<W; j+=2) {
         if (--b == 0)
            goto A;
         mas[i][j] = '#';
      }
   }
A:
   for (int i=H-1; i>=H/2; i-=2) {
      for (int j=0; j<W; j+=2) {
         if (--w == 0) goto B;
         mas[i][j] = '.';
      }
   }
B:
   for (int i=0; i<H; ++i)
      outl(mas[i]);
}



Measured memory_bytes: 256
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        
        String[] input1 = br.readLine().split(" ");
        int n = Integer.parseInt(input1[0]);
        double m = Double.parseDouble(input1[1]);
        
        String[] input2 = br.readLine().split(" ");
        Integer[] votes = new Integer[n];
        
        int voteCount = 0;
        
        for(int i = 0; i < n; i++){
            votes[i] = Integer.valueOf(input2[i]);
            voteCount += votes[i];
        }
        
        Arrays.sort(votes, Collections.reverseOrder());
        
        if(votes[(int)(m - 1)] >= voteCount * (1 / (4 * m))){
            out.println("Yes");
        }else{
            out.println("No");
        }
        
        out.close();
        
    }
}

Measured memory_bytes: 33056
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

string s;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  unordered_map<string, int> ma;
  ma["SUN"] = 7;
  ma["MON"] = 6;
  ma["TUE"] = 5;
  ma["WED"] = 4;
  ma["THU"] = 3;
  ma["FRI"] = 2;
  ma["SAT"] = 1;
  cin >> s;
  cout << ma[s] << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

int main() {
  int n;
  cin >> n;
  vector<int> p(n), q(n);
  rep(i,n) cin >> p[i];
  rep(i,n) cin >> q[i];
  vector<int> a(n);
  rep(i,n) a[i] = i+1;

  map<vector<int>, int> mp;
  do {
    mp[a] = mp.size();
  } while (next_permutation(a.begin(), a.end()));

  int ans = abs(mp[p] - mp[q]);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 5376
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "math.h"
#include "utility"
#include "string"
#include "map"
#include "unordered_map"
#include "iomanip"
#include "random"

using namespace std;
const long long int MOD = 1000000007;

long long int power(long long int x, long long int n, long long int M) {
	long long int tmp = 1;

	if (n > 0) {
		tmp = power(x, n / 2, M);
		if (n % 2 == 0) tmp = (tmp*tmp) % M;
		else tmp = (((tmp*tmp) % M)*x) % M;
	}
	return tmp;
}

long long int N, M, K, Q, W, H, L, R;
long long int ans;


int main() {
	ios::sync_with_stdio(false);
	cin >> N;
	long long int num[51] = {};
	for (int i = 0; i < N; i++) {
		cin >> num[i];
	}
	sort(num, num + N);
	while (1) {
		bool flag = true;
		for (int i = 0; i < N; i++) {
			if (num[i] >= N) {
				flag = false;
				long long int box = (num[i] - N) / N + 1;
				num[i] -= box*N;
				ans += box;
				for (int j = 0; j < N; j++) {
					if (i != j)num[j] += box;
				}
			}
		}
		if (flag)break;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cmath>
using namespace std;
#define LIMIT 35
struct Puzzle{char cont[8]; int space; };
Puzzle puzzle;
int limit,path[LIMIT],MD[8][8];
static const int dx[4] = {-1,0,1,0};
static const int dy[4] = {0,-1,0,1};
static const char direction[4] = {'d','r','u','l'};

int getHeuristic(){
  int sum = 0;
  for(int i=0;i<8;i++){
    if(puzzle.cont[i]=='0')continue;
    sum += MD[i][puzzle.cont[i]-'0'];
  }
  return sum;
}

bool isTarget(){
  for(int i=0;i<8;i++){
    if(puzzle.cont[i] != '0' + i )return false;
  }
  return true;
}

bool dfs(int depth,int prev){
  if(isTarget())return true;
  if(depth+getHeuristic()>limit)return false;

  int px,py,tx,ty;
  Puzzle tmp;
  px = puzzle.space%4;
  py = puzzle.space/4;
  
  
  for(int r=0;r<4;r++){

    tx=px+dx[r];
    ty=py+dy[r];

    if(max(prev,r)-min(prev,r)==2)continue;
    if(tx<0||ty<0||tx>=4||ty>=2)continue;

    tmp=puzzle;

    puzzle.cont[py*4+px] = puzzle.cont[ty*4+tx];
    puzzle.cont[ty*4+tx] = '0';
    puzzle.space = ty*4+tx;

    if(dfs(depth+1,r)){path[depth]=r;return true;}
    puzzle=tmp;
  }
  return false;
}

void solve(){
  for(limit=getHeuristic();limit<=LIMIT;limit+=2){
    if(dfs(0,-100)){
      cout<<limit<<endl;
      //for(int i=0;i<limit;i++)cout<<direction[path[i]];cout<<endl;
      
      return;
    }
  }
  cout<<"unsolvable"<<endl;
}

bool input(){
  for(int i=0;i<8;i++){
    if(cin>>puzzle.cont[i]){}else return false;
    if(puzzle.cont[i]=='0')puzzle.space = i;
  }
  return true;
}

int main(){
  for(int i=0;i<8;i++){
    for(int j=0;j<8;j++){
      MD[i][j]=abs(i/4-j/4)+abs(i%4-j%4);
    }
  }
  while(input()){
    solve();
  }
  return 0;
}

Measured memory_bytes: 1140
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
//<DEFINE>
void Fast() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
}
void File() {
#ifndef ONLINE_JUDGE
	freopen("Input.txt", "r", stdin);
	freopen("Output.txt", "w", stdout);
#endif
}
#ifdef _MSC_VER
#include <intrin.h>
#define __builtin_popcount __popcnt
#ifdef _WIN64
#define __builtin_popcountll __popcnt64
#else
inline int __builtin_popcountll(__int64 a) {
	return __builtin_popcount((unsigned int)a) + __builtin_popcount(a >> 32);
}
#endif
#endif
using ll = long long;
using ull = unsigned long long;
#define mod 1000000007
ll gcd(ll a, ll b) {
	return!b ? a : gcd(b, a % b);
}
#define fix(n) cout << fixed << setprecision(n);
#define all(a) a.begin(), a.end()
#define skip continue
#define stop(n) return cout<<n,0
#define pi  acos(-1)
#define endl "\n"
#define ceil(x,y) (x+y-1)/y
//sin(x* pi / 180)
//be careful from the multiplication while using this define 
//alot of memset may couse TLE
//</DEFINE>
int main() {
	Fast();
	int n;
	cin >> n;
	vector<int>v(n);
	for (int i = 0; i < n; i++)
		cin >> v[i];
	vector<vector<vector<ll>>>dp(n, vector<vector<ll>>(n, vector<ll>(2)));
	for (int i = 0; i < n; i++)
		dp[i][i][1] = v[i], dp[i][i][0] = -v[i];
	for (int i = 1; i < n ; i++)
		for (int l = 0, r = i; r < n; r++, l++) {
			dp[l][r][0] = min(dp[l + 1][r][1] - v[l], dp[l][r - 1][1] - v[r]);
			dp[l][r][1] = max(dp[l + 1][r][0] + v[l], dp[l][r - 1][0] + v[r]);
		}
	cout << dp[0][n - 1][1] << endl;
}

Measured memory_bytes: 495700
#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int main() {
	long long n, count=0;
	cin>>n;
  	map<string, long long> mp;
	for(int i=0;i<n;i++)
	{
		string str;
		cin>>str;
		sort(str.begin(), str.end()); 
       	mp[str]++;
	}
    for (auto x : mp) 
    {
      long long a=x.second;
      count+=((a*(a-1))/2);
    } 
    cout<<count;
	return 0;
}


Measured memory_bytes: 11136
N = int(input())
A = list(map(int, input().split()))

al, ar = [A[0]], [A[-1]]
for n in range(1, N - 1):
	al += [al[-1] + A[n]]
	ar += [ar[-1] + A[-(n + 1)]]
ar = ar[::-1]

ad = []
for n in range(N - 1):
	ad += [abs(al[n] - ar[n])]

#print(al)
#print(ar)
#print(ad)
print(min(ad))


Measured memory_bytes: 37648
#include"bits/stdc++.h"
#include<boost/multi_array.hpp>
#include<boost/range/irange.hpp>
#include<boost/range/algorithm.hpp>
#include<boost/range/adaptors.hpp>

namespace adaptor = boost::adaptors;

void solve()
{
    int64_t N;
    std::cin >> N;
    std::vector<int64_t> a(N);
    for (auto& v : a) std::cin >> v;

    std::vector<int64_t> cum(N + 1);
    cum[0] = 0;
    for (int64_t i = 1; i < N + 1; i++)
    {
        cum[i] = cum[i - 1] + a[i - 1];
    }

    int64_t ans = INT64_MAX;
    for (int64_t i = 1; i < N; i++)
    {
        int64_t x = cum[i];
        int64_t y = cum[N] - x;
        ans = std::min<int64_t>(ans, std::abs(x - y));
    }

    std::cout << ans << std::endl;
}

int main()
{
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    solve();
}


Measured memory_bytes: 6292
#include<bits/stdc++.h>
using namespace std;
int n,k;
int t[100000000];
int check(long long mid){
	int j;
	 j = 0;
	for(int i = 0;i<k;i++){
		int s;
		 s = 0;
		while(s + t[j] <= mid){
			s+= t[j];
			if(j>=n){
				return n;
			}
			j++;
		}
	}
	return j;
}
int aho(){
	long left= 0,right = 1000000000;
	while(right -left>1){
		long long mid;
		mid = (right + left)/2;
		int v;
		 v = check(mid);
		//cout<<left<<" "<<mid<<" "<<right<<endl;
		if(v  == n){
			right = mid;
		}
		else{
			left = mid;
		}
	}
	return right;
}

int main(){
	cin>>n>>k;
	for(int i = 0;i<n;i++){
		cin>>t[i];
	}
	cout<<aho()<<endl;
}


Measured memory_bytes: 3504
require 'pp'
# IS_DEBUG = true
IS_DEBUG = false
def dputs str
	if(IS_DEBUG)
		puts str
	end
end
def dpp str
	if(IS_DEBUG)
		pp str
	end
end

N,d=gets.chomp.split(' ').map{|n| n.to_i}
X = Array.new(N)
X=gets.chomp.split(' ').map{|n| n.to_i}
Xsorted=X.sort
a = Xsorted[N/2-1]
b = Xsorted[N/2]
if(a==b)
	0.upto(N-1){|i|
		puts a
	}
else
	0.upto(N-1){|i|
		if(X[i] <= a)
			puts b
		elsif(X[i] >= b)
			puts a
		end
	}
end


Measured memory_bytes: 27240
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, K = map(int, input().split())
    A = list(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    ans=0

    maxn=N
    fact=[1]*(maxn+1)#NはnCrの最大のn
    invs=[1]*(maxn+1);invs[0]=0
    ifact=[1]*(maxn+1)
    for i in range(2,maxn+1):
        fact[i]=(fact[i-1]*i)%mod
        invs[i]=invs[mod%i]*(-(mod//i))%mod
        ifact[i]=(ifact[i-1]*invs[i])%mod
    def perm(n,r): return fact[n]*ifact[n-r]%mod
    def comb(n,r):
        if r>n:return 0 
        return (fact[n]*ifact[r]%mod)*ifact[n-r]%mod
    def multicomb(self,n,*rs):#n!/(r1!*r2!*r3!*...)
        ans=fact[n]
        for r in rs: ans=(ans*self.ifact[r])%self.mod
        return ans
    
    A.sort()
    for i in range(N):
        ans-=A[i]*comb(N-i-1,K-1)
        ans%=mod
    for i in range(N-1,-1,-1):
        ans+=A[i]*comb(i,K-1)
        ans%=mod
    print(ans)
        


if __name__ == "__main__":
    main()

Measured memory_bytes: 93300
# by the authority of GOD     author: manhar singh sachdev #

import os,sys
from io import BytesIO, IOBase

def main():
    s = input().strip()
    cou=maxi=0
    for i in s:
        if i=='R':
            cou += 1
        else:
            maxi = max(maxi,cou)
            cou = 0
    maxi = max(maxi,cou)
    print(maxi)
#Fast IO Region
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == '__main__':
    main()

Measured memory_bytes: 62592
n = int(input())
a = list(map(int,input().split()))
dist = [0]*100000
ans = sum(a)
for i in a:
    dist[i-1] += 1

q = int(input())
for i in range(q):
    b,c = map(int,input().split())
    if dist[b-1] != 0:
        dist[c-1] += dist[b-1]
        ans += dist[b-1] * (c-b)
        dist[b-1] = 0
    print(ans)

Measured memory_bytes: 21032
# -*- coding: utf-8 -*-
import sys
from time import time, sleep
from random import random
from bisect import bisect, bisect_left
def inpl(): return list(map(int, input().split()))
N, H, W = inpl()
cnt = 0
for _ in range(N):
    a, b = inpl()
    if a>=H and b>=W:
        cnt += 1
print(cnt)

Measured memory_bytes: 9436
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
	ll i,j,k,m,n,t;
	ll a,b,c,d;
	cin>>a>>b>>c>>d;
	ll mx=-1*LLONG_MAX;
	mx=max(mx,a*c);
	mx=max(mx,a*d);
	mx=max(mx,b*c);
	mx=max(mx,b*d);
	cout<<mx;
}

Measured memory_bytes: 3632
def main():
    N = str(input())
    n_len = len(N)
    tmp = 0
    for i in range(0,n_len):
        tmp += int(N[i])
    if tmp % 9 == 0:
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()


Measured memory_bytes: 9292
#include<bits/stdc++.h>
using namespace std;
int n;
long long a[101010],mn=1e10+11,ans,cnt;
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		mn=min(abs(a[i]),mn);
		if(a[i]<0)
		{
			cnt++;
		}
	}
	for(int i=0;i<n;i++)
	{
		if(a[i]<0)
		{
			mn=-mn;
			break;
		}
	}
	for(int i=0;i<n;i++)
	{
		ans+=abs(a[i]);
	}
	if(mn<0 && cnt%2)
	{
		ans+=mn*2;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1024
#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <bitset>
#include <complex>
#include <unistd.h>
#include <cassert>
#include <cctype>
#include <random>
#include <time.h>
#define _USE_MATH_DEFINES
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> plglg;
typedef pair<double, ll> pdlg;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlglglg;
typedef tuple<double, double, double> tddd;
typedef complex<double> xy_t;
typedef vector<ll> vll;
typedef vector< vector<ll> > matrix;
#define REP(i, x, y) for(ll i = (ll)x; i < (ll)y; i++)
#define DREP(i, x, y, d) for(ll i = (ll)x; i < (ll)y; i += (ll)d)
#define PER(i, x, y) for(ll i = (ll)x; i > (ll)y; i--)
#define DPER(i, x, y, d) for(ll i = (ll)x; i > (ll)y; i -= (ll)d)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
double pi = 3.141592653589793;
ll mod = 1000000007;
int intmax = 2147483647;
int intmin = -2147483648;
ll llmax = 9223372036854775807;
ll llmin = -9223372036854775807;
int iinf = intmax / 8;
ll inf = llmax / 8;
double eps = 1e-11;

ll N;
double dp[310][310][310];

double rec(ll i, ll j, ll k) {
    if (dp[i][j][k] > 0) {
        return dp[i][j][k];
    }
    if (i == 0 && j == 0 && k == 0) {
        return 0.0;
    }

    double res = 0.0;
    double sum = i + j + k;
    if (i > 0) {
        res += rec(i - 1, j, k) * i / sum;
    }
    if (j > 0) {
        res += rec(i + 1, j - 1, k) * j / sum;
    }
    if (k > 0) {
        res += rec(i, j + 1, k - 1) * k / sum;
    }
    res += N / sum;

    return dp[i][j][k] = res;
}

int main() {
    cin >> N;
    ll num[3];
    fill(num, num + 3, 0);
    ll sum = 0;
    REP(i, 0, N) {
        ll a;
        cin >> a;
        num[a - 1]++;
        sum += a;
    }
    REP(i, 0, 310) {
        REP(j, 0, 310) {
            fill(dp[i][j], dp[i][j] + 310, 0);
        }
    }
    double ans = rec(num[0], num[1], num[2]);
    cout << setprecision(12);
    cout << ans << endl;
}


Measured memory_bytes: 233088
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pint = pair<int,  int>;
using edge = int;
using graph = vector<vector<edge>>;
const ll INF = 1LL << 60;
const int INF32 = 1 << 29;
const ll MOD = 1000000007;


int main() {
	ll  n; cin >>n;
	ll ans = 0;
	ans+=(n/11)*  2;
	if(n%11!=0){
	if(n%11<=6){ans++;}
	else{ans+=2;}
	}
	
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main() {
	long long int **line;
	int size;
	cin >> size;
	line = new long long int*[size + 2];
	long long int *hako;
	hako = new long long int[size + 1];
	for (int i = 0; i < size + 2; ++i) {
		line[i] = new long long int[3];
		line[i][0] = i;
		line[i][1] = i - 1;
		line[i][2] = i + 1;
	}
	long long int answer=0;
	int dummy;
	for (int i = 1; i <= size; ++i) {
		cin >> dummy;
		hako[dummy] = i;
	}
	for (int i = size; i >= 1; --i) {
		answer += (hako[i] - line[hako[i]][1])*(line[hako[i]][2] - hako[i])*i;
		line[line[hako[i]][1]][2] = line[hako[i]][2];
		line[line[hako[i]][2]][1] = line[hako[i]][1];
		delete[] line[hako[i]];
	}

	cout << answer << endl;
	delete[] line;
	delete[] hako;
	return 0;
}

Measured memory_bytes: 9600
#include<bits/stdc++.h>
using namespace std;

int main() {
    long long N, M;
    cin >> N >> M;
    vector <bool> dp(N+1, true);
    vector <long long> wa(N+1, 0);
    long long AC=0;
    long long WA=0;
    for (long long i=0; i<M; i++) {
        long long p;
        string S;
        cin >> p >> S;
        if(S=="WA" && dp.at(p)) wa.at(p)++;
        else if (S=="AC" && dp.at(p)) {
            dp.at(p) = false;
            AC++;
        }
    }
    for (long long i=1; i<N+1; i++) {
        if (!dp.at(i)) WA+=wa.at(i);
    }
    cout << AC << " " << WA << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define MOD 1000000007
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
using P = pair<int,int>;

ll dp[100010]={0};

int main()
{
  ll N, M;
  cin >> N >> M;
  dp[0]=1;
  dp[1]=1;
  FOR(i,2,N+1){
    dp[i]=(dp[i-1]+dp[i-2])%MOD;
  }
  if(M!=0){
    vector<int> A(M);
    REP(i, M) cin >> A[i];
    
    ll ans=dp[A[0]-1];
    int flag = 0;
    REP(i,M-1){
      if(A[i]+1==A[i+1]){
        flag = 1;
        break;
      }else{
        ans=((ans%MOD)*(dp[A[i+1]-1-A[i]-1]%MOD))%MOD;
      }
    }
    ans=((ans%MOD)*(dp[N-A[M-1]-1]%MOD))%MOD;

    if(flag == 1){
      cout << 0 << endl;
    }else{
      cout << ans << endl;
    }
  }else{
    cout << dp[N] << endl;
  }
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define ps push
#define pf push_front
#define mp make_pair
#define And &&
#define Or ||
#define ppb pop_back
#define ppf pop_front
#define inf INT_MAX
#define sz(name) name.size()
#define len(name) name.length()
#define ig cin.ignore()
#define Sort(name) sort(name.begin(),name.end())
#define For(name,start,finish) for(int name=start;name<finish;name++)
#define fast_in_out ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

//int row[]={-1,0,1,0};
//int col[]={0,1,0,-1};

const ll N=1e4+10;
const ll M=1e9+7;

ll Max(ll a,ll b){if(a>b)return a;return b;}
ll Min(ll a,ll b){if(a>b)return b;return a;}
ll big_mul(ll a,ll b,ll m){ll x=0,y=a%m;while(b>0){if(b&1)x=(x+y)%m;y=(2*y)%m;b>>=1;}return x%m;}
ll big_mod(ll a,ll b,ll m){ll x=1,y=a%m;while(b>0){if(b&1)x=(x*y)%m;y=(y*y)%m;b>>=1;}return x%m;}
ll Big_mod(ll a,ll b,ll m){ll x=1,y=a%m;while(b>0){if(b&1)x=big_mul(x,y,m);y=big_mul(y,y,m);b>>=1;}return x%m;}
ll mod_inverse(ll a,ll m){return big_mod(a,m-2,m);}  //a^-1 mod m = a^(m-2) mod m

bool fnct(int pos1,int pos2,string s1,string s2,int k)
{

    for(int i=pos1;i<=pos2;i++,k++)
    {
        if(s1[i]!=s2[k])
        return false;
    }

    return true;
}

int main()
{
    fast_in_out;

    string s1,s2;
    cin>>s1>>s2;

    For(i,0,sz(s1))
    {
        if(fnct(i,sz(s1)-1,s1,s2,0)==true And fnct(0,i-1,s1,s2,sz(s1)-i)==true)
        {
            cout<<"Yes"<<endl;
            return 0;
        }
    }

    cout<<"No"<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <cctype>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <complex>
#include <fstream>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T> T RoundOff(T a){ return int(a+.5-(a<0)); }
template<class T, class C> void chmax(T& a, C b){ if(a < b) a = b; }
template<class T, class C> void chmin(T& a, C b){ if(b < a) a = b; }
template<class T, class C> pair<T, C> mp(T a, C b){ return make_pair(a, b); }
bool check(vint aa, vint mm);
ll gcd(ll x, ll y);
ll lcm(ll x, ll y);
ll cnt(ll a, ll m);

bool check(vint aa, vint mm)
{
    rep(i, 3)
        if(aa[i] != 0 || mm[i] != 0)
            return true;
    
    return false;
}
//! gcd

ll gcd(ll x, ll y)
{    return y ? gcd(y, x % y) : x;	}


//! lcm
ll lcm(ll x, ll y)
{    return x * y / gcd(x, y);		}

ll cnt(ll a, ll m)
{
    ll n = 1, res = 0;
    
    do 
    {
        res++;
        
        n = a * n % m;
    }
    while(n != 1);
    
    return res;
}


int main()
{
    vint a(3), m(3);
    
    while(true)
    {
        rep(i, 3)
            cin >> a[i] >> m[i];
        
        if (!check(a, m))
            break;
        
        cout << lcm(cnt(a[0], m[0]), lcm(cnt(a[1], m[1]), cnt(a[2], m[2]))) << endl;
    }
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < int(n); ++ (i))
#define REP_R(i, n) for (int i = int(n) - 1; (i) >= 0; -- (i))
using namespace std;

template <typename R>
void fft_inplace(vector<complex<R> > & f, int dir) {
    int n = f.size();
    assert(n == pow(2, log2(n)));
    R theta = dir * 2 * M_PI / n;
    for (int m = n; m >= 2; m >>= 1) {
        REP (i, m / 2) {
            complex<R> w = polar<R>(1, i * theta);
            for (int j = i; j < n; j += m) {
                int k = j + m / 2;
                complex<R> x = f[j] - f[k];
                f[j] += f[k];
                f[k] = w * x;
            }
        }
        theta *= 2;
    }
    int i = 0;
    REP3 (j, 1, n - 1) {
        for (int k = n >> 1; k > (i ^= k); ) k >>= 1;
        if (j < i) {
            swap(f[i], f[j]);
        }
    }
}
template <typename T, typename R = long double>
void convolution_self_inplace(vector<T> & a, int result_n) {
    int m = 2 * a.size() - 1;
    int n = pow(2, ceil(log2(m)));
    vector<complex<R> > x(n);
    copy(a.begin(), a.end(), x.begin());
    fft_inplace(x, +1);
    vector<complex<R> > z(n);
    REP (i, n) x[i] *= x[i];
    fft_inplace(x, -1);
    a.resize(result_n);
    REP (i, result_n) a[i] = x[i].real() / n;
}

int main() {
    // input
    int n; scanf("%d", &n);
    // solve
    const int height = min(n, 50);
    vector<long double> dp(n + 1);
    dp[0] = 1;
    long double last_dp_n = 0;
    REP3 (j, 1, height + 1) {
        convolution_self_inplace(dp, n + 1);
        REP_R (i, n) {
            dp[i + 1] = dp[i] / (i + 1);
        }
        dp[0] = 1;
        // output
        printf("%.10lf\n", double(dp[n] - last_dp_n));
        last_dp_n = dp[n];
    }
    REP3 (j, height + 1, n + 1) {
        printf("0\n");
    }
    return 0;
}

Measured memory_bytes: 7936
N = int(input())
s = [int(input()) for _ in range(N)]

s.sort()
ans = sum(s)

i = 0
while ans % 10 == 0:
    if i >= len(s):
        print(0)
        exit()
    if not s[i] % 10 == 0:
        ans -= s[i]
    i += 1

print(ans)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb             push_back
#define conv(a)        bitset<30>(a).to_string() ;
#define mxpq           priority_queue <int>
#define mnpq           priority_queue<int,vector<int>,greater<int>>
#define S(v)           sort(v.begin(),v.end())
#define RS(v)          sort(v.rbegin(),v.rend())
#define R(v)           reverse(v.begin(),v.end())
#define print          printf("%.16f\n", ans)
#define inf            LLONG_MAX
#define mini           LLONG_MIN
#define T              int tc;cin>>tc;while(tc--)
#define MSET(tabl,i)   memset(tabl, i, sizeof(tabl))
#define int            long long 
#define MAXN           10000001
#define M              1000000007
#define fio            cin.sync_with_stdio(false) ; cin.tie(0);cout.tie(0) ;
#define endl           "\n"
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> Set;

void update(int x, int val,vector<int> &BIT,int n)
{
      for(; x <= n; x += x&-x)
        BIT[x] += val;
}
int query(int x,vector<int> &BIT)
{
     int sum = 0;
     for(; x > 0; x -= x&-x)
        sum += BIT[x];
     return sum;
}
void Xarr(){
     
        int n,q; cin>>n>>q ;
        vector<int> v(n+1) ; for(int i=1;i<=n;i++) cin>>v[i] ;
        vector<queue<int>> dp(1000005) ;
        for(int i=1;i<=n;i++) dp[v[i]].push(i) ;
        vector<pair<pair<int,int>,int>> queries(q)  ;
        vector<int> ans(q) ;
        for(int i=0;i<q;i++){
             int l,r  ; cin>>l>>r ;
             queries[i]={{l,r},i} ;
        }
        S(queries) ;
        vector<int> BIT(n+1) ;
        for(int i=0;i<dp.size();i++){
             if(dp[i].empty()) continue ;
             update(dp[i].front(),1,BIT,n) ; 
        }
        int in=1 ;
        for(int i=0;i<queries.size();i++){
               int s=queries[i].first.first ;
               int e=queries[i].first.second ;
               int idx=queries[i].second ;
               while(s!=in){
                   int t=v[in] ;
                   update(in,-1,BIT,n) ;
                   dp[t].pop() ;
                   if(!dp[t].empty()) update(dp[t].front(),1,BIT,n) ;
                   in++ ;
               }
               int f=query(e,BIT) ;
               ans[idx]=f ;
        }

        for(int i=0;i<q;i++) cout<<ans[i]<<endl  ;

 } 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
int32_t main(){
 
    cout<<fixed<<setprecision(16);
    cin.sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
 
    #ifndef ONLINE_JUDGE
     freopen("input.txt",  "r",  stdin);
     freopen("output.txt", "w", stdout);
    #endif
    
    cout << setprecision(9) << fixed;
     clock_t z = clock();
     
     Xarr();
     cerr << "Run Time : " << ((double)(clock() - z) / CLOCKS_PER_SEC);
 
     return 0;

}

Measured memory_bytes: 703524
#include <bits/stdc++.h>
using namespace std;
const long double PI = acos(-1);
typedef long long ll;
typedef pair<int64_t,int64_t> pll;
typedef pair<int,int> pii;
typedef vector<int64_t> vl;
int dx[]={1,-1,0,0,1,-1,1,-1};
int dy[]={0,0,1,-1,1,-1,-1,1};
#define INF (2147483647)
#define mod (1000000007)
#define limit (7368791)
#define rep(i,a,b) for (int64_t i = (a); i < (b); i++)
#define REP(i,n) rep(i,0,n)
#define sz(s) (s).size()
#define ALL(a) begin(a),end(a)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second


void solve()
{
    int n;cin>>n;
    string s;cin>>s;
    int ans=0;
    REP(i,1000){
        int now=0;
        int64_t t[3] = {i / 100, (i / 10) % 10, i % 10};
        REP(j,n){
            if(s[j]==('0'+t[now]))now++;
            if(now==3){ans++;break;}
        }
    }
    cout<<ans<<endl;
}

int main()
{
    cin.tie(0);
	ios::sync_with_stdio(false);
    solve();
    return 0;
}


Measured memory_bytes: 384
#include<cstdio>
#include<cstdlib>
#include<cstring>

struct Node
{
	int key;
	Node *next, *prev;
};

Node *nil;

Node* listSearch(int key) {
	Node *cur = nil->next;
	while (cur != nil && cur->key != key) {
		cur = cur->next;
	}
	return cur;
}

void init() {
	nil = (Node *)malloc(sizeof(Node));
	nil->next = nil;
	nil->prev = nil;
}

void printfList() {
	Node *cur = nil->next;
	int isf = 0;
	while (1) {
		if (cur == nil) break;
		if (isf++ > 0) printf(" ");
		printf("%d", cur->key);
		cur = cur->next;
	}
	printf("\n");
}

void deleteNode(Node *t) {
	if (t == nil) return;
	t->prev->next = t->next;
	t->next->prev = t->prev;
	free(t);
}

void deleteFirst() {
	deleteNode(nil->next);
}

void deleteLast() {
	deleteNode(nil->prev);
}

void deleteKey(int key) {
	deleteNode(listSearch(key));
}

void insert(int key) {
	Node *x = (Node *)malloc(sizeof(Node));
	x->key = key;
	x->next = nil->next;
	nil->next->prev = x;
	nil->next = x;
	x->prev = nil;
}

int main() {
	int key, n, i;
	int size = 0;
	char com[20];
	int np = 0, nd = 0;
	scanf("%d", &n);
	init();
	for (i = 0; i < n; i++) {
		scanf("%s%d", com, &key);
		if (com[0] == 'i') {
			insert(key);
			np++;
			size++;
		}
		else if (com[0] == 'd') {
			if (strlen(com) > 6) {
				if (com[6] == 'F') deleteFirst();
				else if (com[6] == 'L') deleteLast();
			}
			else {
				deleteKey(key);
				nd++;
			}
			size--;
		}
	}
	printfList();
	return 0;
}


Measured memory_bytes: 33816
n = int(input())
h = [int(x) for x in input().split()]

ans = 0

def water(h):
   global ans

   if (len(h) == 0):
      return
   if (len(h) == 1):
      ans += h[0]
      return

   m = min(h)
   ans += m
   h = [i - m for i in h]
   while (0 in h):
      water(h[:h.index(0)])
      h = h[h.index(0)+1:]
   water(h)


water(h)
print(ans)


Measured memory_bytes: 3064
#include <cstdio>
#include <iostream>
#include <string>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>

const long long INF = 1000000007;

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int , pii> piii;
typedef pair<pii, pii> piiii;

int n;
int comp[3011];
int dp[3011][3011];

int main() {
	scanf("%d", &n);
	string s;
	cin >> s;
	for (int i = 1; i < n; i++) {
		if (s[i - 1] == '<') comp[i] = 0;
		else comp[i] = 1;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) dp[i][j] = 0;
	}

	dp[1][1] = 1;
	for (int i = 2; i <= n; i++) {
		if (comp[i - 1] == 0) {
				int sum = 0;
				for (int k = 1; k < i; k++) {
					sum = (sum + dp[i - 1][k]) % INF;
					dp[i][k + 1] = sum;
				}
			}
		else {
				int sum = 0;
				for (int k = i - 1; k >= 1; k--) {
					sum = (sum + dp[i - 1][k]) % INF;
					dp[i][k] = sum;
				}
			}
	}
	int sum = 0;
	for (int i = 1; i <= n; i++) sum = (sum + dp[n][i]) % INF;
	printf("%d\n", sum);
}


Measured memory_bytes: 35584
N, M = map(int, input().split())

def get_divisor(n):
    '''nの約数を返す
    '''
    d = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            d.add(i)
            d.add(n//i)
    return d

D = list(get_divisor(M))
D.sort(reverse=True)

ans = 0
for d in D:
    if M//d < N:
        continue
    ans = d
    break

print(ans)


Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
#define PRINT(v) for (auto x : (V)) cout <<x <<" " <<endl;
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
const ll MOD = 1000000007;
const ll INF = 10000000000000000;
vector<int> x4 = {0, 1, 0, -1}, x8 = {0, 1, 1, 1, 0, -1, -1, -1};
vector<int> y4 = {1, 0, -1, 0}, y8 = {1, 1, 0, -1, -1, -1, 0, 1};
template<class T> struct edge { int from, to; T cost;};
template<class T> inline bool chmin(T& a, T b){if (a>b){a = b; return true;}return false;}
template<class T> inline bool chmax(T& a, T b){if (a<b){a = b; return true;}return false;}
template<class T> inline T powerM(T a,T b){if (b==0) return 1;
T tmp = powerM(a,b/2); if (b%2==0) return tmp*tmp%MOD; else return tmp*tmp%MOD*a%MOD; }
template<class T> inline T power(T a,T b,T m){ if (b==0) return 1;
  T tmp = power(a,b/2,m); if (b%2==0) return tmp*tmp%m; else return tmp*tmp%m*a%m; }
template<class T> inline T gcd(T a, T b){if (b==0) return a; return gcd(b, a%b);}
template<class T> inline T lcm(T a, T b){return a / gcd(a,b) * b;}
// ax+by=gcd(a,b)を解く
template<class T> inline T extgcd(T a,T b,T &x,T &y){if (b==0){x=1; y=0; return a;} T d=extgcd(b,a%b,y,x); y -= a/b*x; return d;}
void hey(){ cout <<"hey" <<endl; }


int main() {
  int n; cin >>n;
  set<string> S;
  rep(i, n){
    string s; cin >>s;
    S.insert(s);
  }
  cout <<S.size() <<endl;
}

Measured memory_bytes: 19180
#include<bits/stdc++.h>
using namespace std;

int main(){
	string s1,s2;
	cin >> s1 >> s2;
	int num=0;
	for(int i=0;i<3;i++){
		if(s1[i] == s2[i])
			num++;
	}
	cout << num << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <math.h>
#include <set>

using namespace std;

void C(void) {
	long long n, m, q;
	long long i, j, k;
	long long temp_a, temp_b, temp_c, temp_d;
	vector<long long> a, b, c, d;

	cin >> n >> m >> q;

	for (i = 0; i < q; i++) {
		cin >> temp_a, temp_b, temp_c, temp_d;
		a.push_back(temp_a);
		b.push_back(temp_b);
		c.push_back(temp_c);
		d.push_back(temp_d);
	}

}


int main(void) {
	long long n, m, q;
	long long i, j, k;
	long long a, b;
	long long max = 0;

	cin >> a >> b >> n;


	if (b > n) {
		max = floor((a * n) / double(b)) - a * floor(n / double(b));
	}
	else {
		max = floor((a * (b - 1)) / double(b)) - a * floor((b - 1) / double(b));
	}


	cout << max << endl;


	return 0;
}


Measured memory_bytes: 3636