akhauriyash/Code-Regression huggingface dataset:
n, h = map(int, input().split())

ab = [list(map(int, input().split())) for _ in range(n)]
a_max = sorted(ab, key=lambda x: x[0], reverse=True)[0][0]
ab_sorted = sorted(ab, key=lambda x: x[1], reverse=True)

ans = 0
# a_maxよりも高い攻撃力の刀を投げつける
for i in range(n):
    if a_max > ab_sorted[i][1]:
        break
    h = h - ab_sorted[i][1]
    ans += 1
    if h <= 0:
        print(ans)
        exit(0)

# 引き算だとめっちゃ時間がかかるので割り算で斬りかかる数を求める
add = h//a_max if h % a_max == 0 else h//a_max + 1
print(ans + add)

Measured memory_bytes: 29800
n=int(input())
line1=list(map(int,input().split()))
line2=list(map(int,input().split()))
line=[line1,line2]
point=0
place=0
def judge(i):
  status1=0
  status2=0
  possible=1
  for k in range(n-i-1):
    status1+=line[0][i+k+1]
    status2+=line[1][i+k]
    if status1>=status2:
      possible=0
      break
  return possible
for i in range(n):
  point+=line[place][i]
  if place==0 and judge(i)==1:
    place=1
    point+=line[place][i]
print(point)


Measured memory_bytes: 3064
#include <stdio.h>

main()
{
int N, M;

scanf("%d %d", &N, &M);

int A[N];
int sum = 0;
int max = 0;

for (int i=0; i<N; i++)
{
	scanf("%d", &A[i]);
	sum += A[i];
	if (A[i] > max) { max = A[i]; }
	//printf("%d %d\n", A[i], max);
}


float thresh = (float)sum / (4 * M);
//printf("%f\n", thresh);

int selectable = 0;
for (int i=0; i<N; i++)
{
	if ((float)(A[i]) >= thresh) { selectable++; }
}
//printf("%d\n", selectable);

if (selectable >= M)
{
	printf("Yes");
}
else
{
	printf("No");
}
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#define  lowbit(x) (x&(-x))
#define  ll long long
#define  ull unsigned long long
#define  max(a,b) (a>b?a:b)
#define  min(a,b) (a>b?b:a)
#define  PI acos(-1.0)
#define  fir first
#define  sec second
#define  SZ(x) (x.size())
#define  inf 0x3f3f3f3f
#define  PB push_back
#define  MP make_pair
#define  all(x) (x).begin(),(x).end()
#define  PII pair<int,int>
#define  E 2.7182818284590452353602874713527
using namespace std;

/**********************************************Head-----Template****************************************/
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
//const ll mod = 10000019;
//const ll phi_mod_prime=mod-1;
ll ksm(ll a,ll b,ll mod){ll ans=1;a%=mod;assert(b>=0);for(;b;b>>=1){if(b&1) ans=ans*a%mod;a=a*a%mod;}return ans;}
ll phi(ll n){ ll rea=n;for(ll i=2;i*i<=n;i++){if(n%i==0){ rea=rea-rea/i;while(n%i==0) n/=i;}}if(n>1) rea=rea-rea/n;return rea;}
//a^(b%phi(mod)+phi(mod))%mod;
void exgcd(int a,int b,int &x,int &y,int &d){if(!b){x=1;y=0;d=a;}else exgcd(b,a%b,y,x,d),y-=a/b*x;}
inline int inv(int a,int p){int x,y,d;exgcd(a,p,x,y,d);x=(x%p+p)%p;return x;}
/********************************Head----Template**********************************************/

int main (){
ll n;cin>>n;
cout<<(n-2)*180<<endl;
    return 0;
}



Measured memory_bytes: 256
#include<stdio.h>
#include<limits.h>

#define rep( i ,end ) for( int i = 0 ; i < end ; ++i )
#define Nmax 100
#define INF ( INT_MAX / 10 )

int Node[ Nmax ][ Nmax ] ;

int min( int a ,int b )
{
	return a > b ? b : a ;
}

void Init( int NODE[ Nmax ][ Nmax ] ,int N )
{
	rep( i ,N )
	{
		rep( j ,N )
		{
			NODE[ i ][ j ] = ( i == j ) ? 0 : INF ;
		}
	}
}



int main( void )
{
	int N ,V ,K ;
	int v ,cost ;
	scanf( "%d" ,&N ) ;

	Init( Node ,N ) ;

	rep( i ,N )
	{
		scanf( "%d %d" ,&V ,&K ) ;

		rep( j ,K )
		{
			scanf( "%d %d" ,&v ,&cost ) ;

			Node[ V ][ v ] = cost ;
		}
	}

	rep( u ,N )
	{
		rep( i ,N )
		{
			rep( j ,N )
			{
				Node[ i ][ j ] = min( Node[ i ][ j ] ,Node[ i ][ u ] + Node[ u ][ j ] ) ;
			}
		}
	}

	rep( u ,N )
	{
		printf( "%d %d\n" ,u ,Node[ 0 ][ u ] ) ;
	}

	return 0 ;
}


Measured memory_bytes: 2720
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <functional>
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    string S; cin >> S;
    int ans = N;
    int L = 0, R = 0;
    rep(i, S.length()) {
        if(S[i] == 'W') L++;
        else R++;
    }
    rep(i, S.length()) {
        if(S[i] == 'W') L--;
        else R--;

        ans = min(ans, R);

        if(S[i] == 'W') R++;
        else L++;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3868
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int n;
	cin >> n;
	
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a.at(i);
	}

	auto count1 = count_if(a.cbegin(), a.cend(), [](int x) { return x % 2 == 0; });

	auto count2 = 0;
	for (auto t : a) {
		if (t % 2 == 0) {
			if (t % 3 == 0 || t % 5 == 0) {
				count2++;
			}
		}
	}

	if (count1 == count2) {
		cout << "APPROVED";
	}
	else {
		cout << "DENIED";
	}

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	string in;
	int set=0;
	cin>>in;
	for (int i = 0; i < in.length(); ++i)
	{
		if(in[i]=='9'){
			set=1;
			break;
		}
	}
	if(set==1){
		cout<<"Yes"<<"\n";
	}
	else{
		cout<<"No"<<"\n";
	}

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin >> s;
  if(s.at(1) == 'B'){ 
    s.at(1) = 'R';
  }
  else{
    s.at(1) = 'B';
  }
  cout << s << endl;
}

    

Measured memory_bytes: 3600
import math

A,B,H,M = map(int, input().split())
AR = 360*H/12+30*M/60
BR = 360*M/60

if abs(AR-BR)<180:
  X = abs(AR-BR)
else:
#if abs(AR-BR)>180:
  X = 360-abs(AR-BR)
#else :
#  X = 0

C = A**2+B**2-2*A*B*math.cos(math.radians(X))
print(C**0.5)  

Measured memory_bytes: 9520
#!/usr/bin/env python
# -*- coding: utf-8 -*-


def main():
    S = input()
    T = input()

    s = len(S)
    t = len(T)

    ans = t

    for i in range(s - t + 1):
        tmp = 0
        for j in range(t):
            if S[i + j] != T[j]:
                tmp += 1
        ans = min(ans, tmp)

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9032
d = int(input())
c = list(map(int,input().split()))
s = []
p = [1]*d
for i in range(d):
    s.append(list(map(int,input().split())))
x = [1]*26
for i in range(d):
    q = 1
    m = -1
    for j in range(26):
        n = s[i][j] + (x[j]+13)*(x[j]+14)*c[j]
        x[j] += 1
        if(m < n):
            m = n
            q = j
    x[q] *= 0
    p[i] = q+1
for i in range(d):
    print(p[i])

Measured memory_bytes: 68208
h, w = map(int, input().split())
s = h * w
if s % 3 == 0:
    ans = 0
else:
    c = []
    for i in range(1, h):
        sa = i * w
        sb = (h - i) * (w // 2)
        sc = (h - i) * (w - (w // 2))
        min_s = min(sa, min(sb, sc))
        max_s = max(sa, max(sb, sc))
        c.append(max_s - min_s)
        sb = ((h - i) // 2) * w
        sc = s - sa - sb
        min_s = min(sa, min(sb, sc))
        max_s = max(sa, max(sb, sc))
        c.append(max_s - min_s)
    for i in range(1, w):
        sa = i * h
        sb = (w - i) * (h // 2)
        sc = (w - i) * (h - (h // 2))
        min_s = min(sa, min(sb, sc))
        max_s = max(sa, max(sb, sc))
        c.append(max_s - min_s)
        sb = ((w - i) // 2) * h
        sc = s - sa - sb
        min_s = min(sa, min(sb, sc))
        max_s = max(sa, max(sb, sc))
        c.append(max_s - min_s)
    ans = min(c)
print(ans)

Measured memory_bytes: 18928
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, h;
    cin >> n >> h;
    VI b(n);
    int a_max = 0;
    REP(i, n) {
        int a;
        cin >> a >> b[i];
        a_max = max(a_max, a);
    }
    
    sort(ALL(b));
    auto it = lower_bound(ALL(b), a_max);
    int use_index = distance(b.begin(), it);
    ll b_sum = 0;

    FOR(i, use_index, n - 1) b_sum += b[i];
    int ans = 0;
    if(h <= b_sum) {
        FORR(i, n - 1, use_index) {
            h -= b[i];
            ans++;
            if(h <= 0) break;
        }
    } else {
        h -= b_sum;
        ans = n - use_index;
        ans += (h + a_max - 1) / a_max;
    }
    cout << ans << endl;
    return 0;
}


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

int main(void) {
    string str;
    cin>>str;
    bool flag=true;
    for(int i=0;i<(int)str.size()-1;i++) {
        if((int)str.find(str[i],i+1)==-1 && flag) flag=true;
        else flag=false;
    }
    if(flag) cout<<"yes"<<endl;
    else cout<<"no"<<endl;

    return 0;
}


Measured memory_bytes: 256
def main():
    from sys import stdin
    input = stdin.readline

    n, m = map(int, input().split())
    s, t = map(lambda x: int(x)-1, input().split())
    g = [[] for _ in [0]*n]
    for i in range(m):
        a, b, c = map(int, input().split())
        g[a-1].append((b-1, c))
        g[b-1].append((a-1, c))

    import heapq
    inf = 10**16
    short = inf
    mod = 10**9+7

    dist_s = [inf]*n
    dp_s = ([0]*n)+[1]
    h = [(0, s, -1)]
    heapq.heapify(h)
    while h:
        d, i, a = heapq.heappop(h)
        if d > short:
            break
        elif i == t:
            short = d
        d2 = dist_s[i]
        if d2 == inf:
            dist_s[i] = d
            dp_s[i] = dp_s[a]
            for j, k in g[i]:
                if dist_s[j] == inf:
                    heapq.heappush(h, (d+k, j, i))
        elif d2 == d:
            dp_s[i] = (dp_s[i]+dp_s[a]) % mod

    dist_t = [inf]*n
    dp_t = ([0]*n)+[1]
    h = [(0, t, -1)]
    heapq.heapify(h)
    while h:
        d, i, a = heapq.heappop(h)
        if d > short:
            break
        d2 = dist_t[i]
        if d2 == inf:
            dist_t[i] = d
            dp_t[i] = dp_t[a]
            for j, k in g[i]:
                if dist_t[j] == inf:
                    heapq.heappush(h, (d+k, j, i))
        elif d2 == d:
            dp_t[i] = (dp_t[i]+dp_t[a]) % mod

    ans = dp_s[t]**2 % mod

    for i, (p, q) in enumerate(zip(dist_s, dist_t)):
        if p+q == short:
            d = p*2
            if d == short and q*2 == short:
                ans = (ans-(dp_s[i]*dp_t[i])**2) % mod
            elif d < short:
                for j, k in g[i]:
                    if d+2*k > short:
                        if d+2*k+2*dist_t[j] == 2*short:
                            ans = (ans-(dp_s[i]*dp_t[j])**2) % mod

    print(ans)


main()


Measured memory_bytes: 79792
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <map>


using namespace std;

int main()
{
	int n;
	
	cin >> n;
	vector < pair<int, int>> pos;
	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		pos.emplace_back(make_pair(x, y));
		//cout << i << endl;
	}

	double sum = 0;
	for (int i = 0; i < n-1; i++) {
		for (int j = i+1; j< n; j++) {
			int rel_x = pos[i].first - pos[j].first;
			int rel_y = pos[i].second - pos[j].second;
			double r = sqrt(rel_x*rel_x + rel_y * rel_y);
			sum += r;
		}
	}

	
	


	double ave = 2 * sum / n;

	printf("%.10lf", ave);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(long long i=0; i<n; i++)
#define Rep(i,n) for(long long i=1; i<n; i++)
#define ll long long
#include <math.h>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <queue>
#include <set>
#include <vector>


using namespace std;
#define PI acos(-1)

int main(){
    ll k;
    cin>>k;
    ll sum=0;
    Rep(i,k+1){
        Rep(l,k+1){
            Rep(m,k+1){
                sum+=gcd(i,gcd(l,m));
            }
        }
    }
   cout<<sum<<endl;
}



Measured memory_bytes: 3648
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(N)]
cd = [list(map(int, input().split())) for i in range(M)]

ans = []
for i, (a, b) in enumerate(ab):
  min_dist = 10**20
  idx = -1
  for j, (c, d) in enumerate(cd):
    dij = abs(a - c) + abs(b - d)
    if dij < min_dist:
      min_dist = dij
      idx = j
  ans.append(idx+1)

print(*ans, sep='\n')

Measured memory_bytes: 3064
def beautiful_strings(w):
    d = {}
    for c in w:
        if c in d:
            d[c] += 1
        else:
            d[c] = 1
    for val in d.values():
        if val % 2 == 1:
            return 'No'
    return 'Yes'

w = input()
print(beautiful_strings(w))


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

int main(){

  int n,count=0;

  cin>>n;

  vector<string> talk(n);

  string ans;

  for(int i=0; i<n; i++){

    cin>>talk.at(i);

  }

  for(int i=0; i<n; i++){

    if(talk.at(i) == "Un" ) count--;

    else if(talk.at(i) == "A") count++;

    if(count < 0 ){

      ans = "NO";

      break;
    } 

  }

  if( ans == "NO" ) cout<<ans<<endl;

  else if( count != 0 ) cout<<"NO"<<endl;

  else cout<<"YES"<<endl;

  return 0;

}


Measured memory_bytes: 3216
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#ifdef ONLINE_JUDGE
#define LLD "%I64d"
#else
#define LLD "%lld"
#endif
#define fu(a,b,c) for(int a=b;a<=(int)c;++a)
#define fd(a,b,c) for(int a=b;a>=(int)c;--a)
#define cu(a,b,c) for(int a=b;a<(int)c;++a)
#define cd(a,b,c) for(int a=(b)-1;a>=(int)c;--a)
#define gcd(a,b) __gcd(a,b) 
#define pii pair<int,int>
#define pll pair<long long,long long>
#define all(a) a.begin(),a.end()
#define F first
#define S second
#define pb push_back
#define pf push_front
#define MOD 1000003 
#define MAXN 52
#define MAXH 20
#define MAXM 52
#define INF 100000000
#define ll long long
#define ull unsigned long long
#define RNG rng mt19937(time(NULL))
#define udist(a,b) uniform_int_distribution<uint32_t> distribution(a,b)
#define max3(a,b,c) max(a, max(b, c))
#define min3(a,b,c) min(a, min(b, c))
#define gmax(a,b) a = max(a, b)
#define gmin(a,b) a = min(a, b)
#define whatis(x) cerr << #x << " is " << x << endl;
#define fast_io() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define PI 3.1415926535897932384626433
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int main(){
	int n,t,a;
	cin >> n >> t >> a;
	int h;
	int cur = -1;
	double dist = MOD;
	fu(i,1,n){
		cin >> h;
		double d = abs(t - h * 0.006 - a);
		if(d < dist){
			cur = i;
			dist = d;
		}
	}
	cout << cur << '\n';
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> p;
    int l;

    for (int i { 0 }; i < n; i++) {
        cin >> l;
        p.push_back(l);
    }

    int matchCount = 0;
    for (int i { 1 }; i < n - 1; i++) {
        if ( (p[i-1] < p[i] && p[i] < p[i+1]) || (p[i+1] < p[i] && p[i] < p[i-1])) {
            matchCount++;
        }
    }

    cout << matchCount << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;

int main(){
  int a,b,c,d;
  int temp;
  while(cin>>temp){
    int count=0;
    for(a=0;a<10;a++){
      for(b=0;b<10;b++){
	for(c=0;c<10;c++){
	  for(d=0;d<10;d++){
	    if(a+b+c+d==temp)count++;
	  }
	}
      }
    }
    cout<<count<<endl;
  }
  return 0;
}

Measured memory_bytes: 1160
function Main(input) {
  "use strict";
  const lines = input.split("\n");
  const N = parseInt(lines[0], 10);
  const As = []
  for (var i = 1; i <= N; i++) {
    As.push(parseInt(lines[i]))
  }
  As.sort((a,b) => b - a)

  var count = 0;
  var prev = -1;
  for (var i = 0; i < N; i++) {
    if (As[i] !== prev) count++
    prev = As[i]
  }
  console.log(count)
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 30464
#include<iostream>
#include<map>
using namespace std;
#define inRange(x,a,b) (a <= x && x < b)

int main(){
    int t;
    cin >> t;

    map<char,int> wj, wi;
    wj['^'] = 0; wi['^'] = -1;
    wj['U'] = 0; wi['U'] = -1;
    wj['v'] = 0; wi['v'] = +1;
    wj['D'] = 0; wi['D'] = +1;
    wj['<'] = -1; wi['<'] = 0;
    wj['L'] = -1; wi['L'] = 0;
    wj['>'] = +1; wi['>'] = 0;
    wj['R'] = +1; wi['R'] = 0;

    map<char,char> enc;
    enc['D'] = 'v';
    enc['U'] = '^';
    enc['L'] = '<';
    enc['R'] = '>';

    while(t-- > 0){
        int h, w;
        cin >> h >> w;

        char mat[h][w];
        int ri, rj, di, dj;
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                cin >> mat[i][j];
                if(wj.count(mat[i][j])) ri = i, rj = j, di = wi[mat[i][j]], dj = wj[mat[i][j]];
            }
        }

        int n;
        string s;
        cin >> n >> s;

        for(char op : s){
            if(op != 'S'){
                di = wi[op], dj = wj[op];
                int ni = ri+di, nj = rj+dj;
                if(inRange(ni, 0, h) && inRange(nj, 0, w) && mat[ni][nj] == '.'){
                    mat[ri][rj] = '.';
                    ri = ni, rj = nj;
                    mat[ri][rj] = enc[op];
                }else{
                    mat[ri][rj] = enc[op];
                }
            }else{
                int si = ri+di, sj = rj+dj;
                while(inRange(si, 0, h) && inRange(sj, 0, w)){
                    if(mat[si][sj] == '*'){
                        mat[si][sj] = '.';
                        break;
                    }
                    if(mat[si][sj] == '#'){
                        break;
                    }
                    si += di, sj += dj;
                }
            }
        }

        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                cout << mat[i][j];
            }
            cout << endl;
        }

        if(t)   cout << endl;
    }

    return 0;
}



Measured memory_bytes: 3072
#include <iostream>
using namespace std;

int main()
{
    string s,t;
    cin >> s;
    cin >> t;
    int ans = 0;

    for (int i = 0; i < s.size(); i++) {
        if (s[i] != t[i])
            ans++;
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3856
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(void){
    int A,B;
    cin>>A>>B;
    int a[3];
    a[0]=A*B;
    a[1]=A+B;
    a[2]=A-B;
    sort(a,a+3);
    cout<<a[2]<<endl;
    
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rg register
#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
using namespace std;
int read() {
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();
	while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
	return f*x;
}
struct node1 {
	int id,v;
} b[200001<<5];
struct node {
	int v,l,r;
} a[200001<<5];
bool cmp(const node1 & a ,const node1 & b ) {
	return a.v<b.v;
}
bool cmp1(const node1 & a ,const node1 & b ) {
	return a.id<b.id;
}
int c[200001<<5],T[200001<<5],d[200001<<5],cnt;
int update(int k,int l,int r,int c) {
	int root=++cnt;
	a[root]=a[k],a[root].v++;
	if(l==r)
		return root;
	int mid=(l+r)>>1;
	if(c<=mid)
		a[root].l=update(a[k].l,l,mid,c);
	else
		a[root].r=update(a[k].r,mid+1,r,c);
	return root;
}
int find(int begin,int end,int l,int r,int k) {
	if(l==r)
		return r;
	int mid=(l+r)>>1;
	int pos=a[a[end].l].v-a[a[begin].l].v;
	if(k<=pos) return find(a[begin].l,a[end].l,l,mid,k);
	else return find(a[begin].r,a[end].r,mid+1,r,k-pos);
}
int main() {
	//file("1");
	int n=read(),tot=0,l,r,k;
	for(int i=1; i<=n; i++)
		b[i].v=read(),b[i].id=i;
	sort(b+1,b+1+n,cmp);
	b[0].v=-2147483647;
	for(int i=1; i<=n; i++)
		b[i].v!=b[i-1].v?c[b[i].id]=++tot,d[c[b[i].id]]=b[i].v:c[b[i].id]=c[b[i-1].id],d[c[b[i].id]]=b[i].v;
	for(int i=1; i<=n; i++)
		T[i]=update(T[i-1],1,n,c[i]);
	sort(b+1,b+1+n,cmp1);
	for(int i=1; i<=n; i++) {
		l=1,r=n,k=n;
		int ans=d[find(T[l-1],T[r],1,n,k)];
		if(ans!=b[i].v)
			cout<<ans<<endl;
		else cout<<d[find(T[l-1],T[r],1,n,k-1)]<<endl;
	}
	return 0;
}


Measured memory_bytes: 57344
s = gets.chomp.chars
r = s.reverse

a = 0
b = 0
ltr = []

for i in 0..(s.size-2)
  if s[i] == 'R'
    a += 1
    if s[i+1] == 'L'
      ltr[i] = a
      ltr[i+1] = b
      a, b = 0, 0
    end
  end
  a, b = b, a
end

a = 0
b = 0
rtl = []

for i in 0..(r.size-2)
  if r[i] == 'L'
    a += 1
    if r[i+1] == 'R'
      rtl[i] = a
      rtl[i+1] = b
      a, b = 0, 0
    end
  end
  a, b = b, a
end

ltr[s.size-1] ||= 0
rtl[r.size-1] ||= 0

ans = ltr.zip(rtl.reverse).map {|x, y| (x || 0) + (y || 0) }

puts ans.join(' ')


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

int main(){
    int n;
    cin>>n;
    vector<int>p(n);
    rep(i,n){
        cin>>p[i];
        p[i]--;
    }
    int cnt=0;
    rep(i,n-1){
        if(p[i]==i){
            swap(p[i],p[i+1]);
            cnt++;
        }
    }
    if(p[n-1]==n-1)cnt++;
    cout<<cnt<<endl;
    return 0;
}

Measured memory_bytes: 640
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
//問題文および制約はちゃんと確認しよう！
//サイズは10^5じゃなくて2×10^5とかかもしれないし、重要な制約・条件を見落としているかも
//とりあえずサンプルを読んでから解法を考えよう？
lint mo=1000000007;
lint zyo(lint x,lint y){
    lint ret=1,a=x;
    while(y>0){
    	if(y%2==1) ret=(ret*a)%mo;
    	a=(a*a)%mo;y/=2;
    }
    return ret;
}
bool ng[100100];
lint dp[100100];
lint num[100100];
vector<lint> so;
int main()
{
	memset(ng,false,sizeof(ng));
	REP(i,2,100050){
		if(ng[i]) continue;
		so.pb(i);
		for(int j=i+i;j<100050;j+=i) ng[j]=true;
	}
	REP(i,2,100050){
		num[i]=1;lint x=i;
		for(int j=0;j<so.size() && so[j]*so[j]<=x;j++){
			//if(x%(so[j]*so[j])==0) num[i]*=0;
			if(x%so[j]==0) num[i]*=-1;
			while(x%so[j]==0) x/=so[j];
		}
		if(x>1) num[i]*=-1;
	}
	//REP(i,2,100) cout<<i<<' '<<num[i]<<endl;
	int k,n;cin>>n>>k;
	lint out=0;
	for(int i=k;i>0;i--){
		dp[i]=zyo(k/i,n);
		//for(int j=0;j<so.size() && so[j]*i<=k;j++)
		for(int j=2;i*j<=k;j++){
			//dp[i]+=num[j]*dp[i*j];
			dp[i]-=dp[i*j];
			dp[i]%=mo;
		}
		out+=dp[i]*i;out%=mo;
		//cout<<i<<' '<<dp[i]<<endl;
	}
	out%=mo;out+=mo;out%=mo;
	cout<<out<<endl;
}


Measured memory_bytes: 5372
// 2部グラフ
#include <bits/stdc++.h>

#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define INF 999999999
#define size_t unsigned long long
#define ll long long
#define rep(i,a) for(int i=0;i<(a);i++)
#define repr(i,a) for(int i=(int)(a)-1;i>=0;i--)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define FORR(i,a,b) for(int i=(int)(b)-1;i>=a;i--)
#define ALL(a) a.begin(), a.end()
using namespace std;
int si() { int x; scanf("%d", &x); return x; }
long long sl() { long long x; scanf("%lld", &x); return x; }
string ss() { string x; cin >> x; return x; }
void pi(int x) { printf("%d ", x); }
void pl(long long x) { printf("%lld ", x); }
void pd(double x) { printf("%.15f ", x); }
void ps(const string &s) { printf("%s ", s.c_str()); }
void br() { putchar('\n'); }

const int MOD = 1e9 + 7;

struct mint {
    int n;
    mint(int n_ = 0) : n(n_) {}
};

mint operator+(mint a, mint b) { a.n += b.n; if (a.n >= MOD) a.n -= MOD; return a; }
mint operator-(mint a, mint b) { a.n -= b.n; if (a.n < 0) a.n += MOD; return a; }
mint operator*(mint a, mint b) { return (long long)a.n * b.n % MOD; }
mint &operator+=(mint &a, mint b) { return a = a + b; }
mint &operator-=(mint &a, mint b) { return a = a - b; }
mint &operator*=(mint &a, mint b) { return a = a * b; }

typedef pair<int, int> P;

const int N = 1e5+5;
string s;
// vector<int> v[N];
int n,u,v,w;
int a[N];

std::vector<P> vec[N];

void dfs(int now, int prev, int value) {
  // cout << now << endl;
  a[now] = value;
  for (auto u: vec[now]) {
    if(u.first != prev) {
      dfs(u.first, now, value ^ (u.second & 1));
    }
  }
}

int main () {
  ios::sync_with_stdio(false); cin.tie(nullptr);
  cin >> n;
  rep(i,n-1) {
    cin >> u >> v >> w;
    vec[u].emplace_back(v,w);
    vec[v].emplace_back(u,w);
  }
  dfs(1, 0 ,0);
  // cout << a[2] << endl;
  rep(i,n) cout << a[i+1] << endl;
}


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

int main(){
    int n, x;
    vector<int> answer;

    int ways;
    while (true)
    {
        ways = 0;
        cin >> n >> x;
        if(n==0 && x==0) break;
        else if (3*(n-1) < x)
        {
            answer.push_back(ways);
        }
        else
        {
            for (int i = 1; i <= n-2; i++)
            {
                for (int j = i+1; j <= n-1; j++)
                {
                    for (int k = j+1; k <= n; k++){
                        if(i+j+k > x) break;
                        else if (i+j+k == x)
                        {
                            ways++;
                        }
                        
                    }
                    
                }
                
            }
            answer.push_back(ways);
        }
        
        
    }
    for (int i = 0; i < answer.size(); i++)
    {
        cout << answer.at(i) << endl;
    }
       
}


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

#define ll long long
#define ld long double
#define mod 1000000007LL
#define INF 1000000011
#define INFLL 1000000000000000011LL
#define endl '\n'
#define vi vector<int>
#define vs vector<string>
#define vll vector<long long>
#define vc vector<char>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pil pair<int, long long>
#define pli pair<long long, int>
#define pcc pair<char, char>
#define pdd pair<double, double>
#define mp make_pair
#define pb(x) push_back(x)
#define fo(i, a, n) for (i = (a); i < (n); i++)
#define foe(i, a, n) for (i = (a); i <= (n); i++)
// clang-format off
#define vin(a) for (ll i = 0; i < sz(a); i++) { cin >> a[i]; } 
#define vout(a) for (auto x : a) { cout << x << " "; }
#define sws                                                                    \
  ios_base::sync_with_stdio(false);                                            \
  cin.tie(0)
// clang-format on
#define pd(x) cout << x
#define sd(x) cin >> x
#define nl cout << endl
#define gcd __gcd
#define all(a) (a).begin(), (a).end()
#define foreach(i, a)                                                          \
  for (__typeof((a).begin()) i = (a).begin(); i != (a).end(); ++i)
#define sz(a) (int)((a).size())
// int dw[8][2]={{0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
void solve() {
  ll x, k, d;
  cin >> x >> k >> d;
  x = abs(x);

  ll s = x / d;

  x -= min(s, k) * d;
  k -= min(s, k);

  if (k % 2 == 0) {
    cout << abs(x) << endl;
  } else {
    cout << abs(x - d) << endl;
  }
}

int main() {
  sws;
  solve();
  return 0;
}

Measured memory_bytes: 3668
#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(v) for(auto x : v){cout << x << " ";} cout << endl
#define printVS(vs) for(auto x : vs){cout << x << endl;}
#define printVV(vv) for(auto v : vv){for(auto&& x : v){cout << x << " ";}cout << endl;}
#define printP(p) cout << p.first << " " << p.second << endl
#define printVP(vp) for(auto p : vp) printP(p);

typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<Pii> vp;
typedef vector<vector<int>> Graph;
const int inf = 1e9;
const int mod = 1e9 + 7;

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int m, nmin, nmax;
    while (cin >> m >> nmin >> nmax, m) {
        vi v(m);
        rep(i, m) cin >> v[i];

        int ma_diff = -1;
        int ans = -1;
        rep2(i, nmin - 1, nmax) {
            if (ma_diff <= v[i] - v[i + 1]) {
                ma_diff = v[i] - v[i + 1];
                ans = i + 1;
            }
        }

        cout << ans << endl;
    }
}

Measured memory_bytes: 3044
#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;

int a[100010];

int main(void){
	int n, l;
	cin >> n >> l;
	rep(i, n) cin >> a[i];

	int idx;
	rep(i, n - 1){
		if(a[i] + a[i + 1] >= l){
			idx = i;
			break;
		}
		if(i == n - 2){
			printf("Impossible\n");
			return 0;
		}
	}
	
	printf("Possible\n");
	//a[i] + a[i + 1] >= lとなる部分だけを残して、周りから削除していく
	//左側から
	for (int i = 0; i < idx; ++i){
		printf("%d\n", i + 1);
	}
	//右側から
	for (int i = n - 2; i > idx; --i){
		printf("%d\n", i + 1);
	}
	//最後
	printf("%d\n", idx + 1);
	return 0;
}

Measured memory_bytes: 1152
#include <stdio.h>

int main(){
	
	long long int n;
	
	scanf("%lld", &n);
	
	long long int hasil;
	
	long long int x=0;
	
	for(int i=1; i<=n; i++){
		
		if(i%3==0 || i%5==0){
			continue;
		}
		
		x=x+i;
		
	}
	
	printf("%lld\n", x);
	
	return 0;
}

Measured memory_bytes: 1728
#include <bits/stdc++.h>
using namespace std;
int num[100005];
bool vst[100005];
int main() {
    int n;
    while(cin >> n) {
        for(int i = 1;i <= n;i++) {
            cin >> num[i];
            vst[i] = false;
        }
        int now = 1;
        int cnt = 0;
        while(!vst[now]) {
            cnt ++;
            vst[now] = true;
            now = num[now];
            if(now == 2) break;
        }
        if(now == 2) printf("%d\n",cnt);
        else puts("-1");
    }
    return 0;
}

Measured memory_bytes: 768
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
typedef long long ll;
typedef unsigned int uint;
using namespace std;

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

    string s;
    cin >> s;

    int ans = 100000;
    for (int i = 0; i < s.length()-2; i++) {
        int tmp = 0;
        tmp += (s.at(i) - '0') * 100;
        tmp += (s.at(i+1) - '0') * 10;
        tmp += (s.at(i+2) - '0') * 1;

        ans = min(ans, abs(753-tmp));
    }

    cout << ans << "\n";
    return 0;
}

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

inline int read() {
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
	return x * f;
}

const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int n, m, s, t, dis[N][3];
vector<int> G[N];

void bfs() {
	memset(dis, -1, sizeof(dis));
	dis[s][0] = 0;
	queue< pair<int, int> > que;
	que.push({s, 0});
	while (!que.empty()) {
		pair<int, int> u = que.front(); que.pop();
		for (auto v : G[u.first]) {
			if (dis[v][(u.second + 1) % 3] < 0) {
				dis[v][(u.second + 1) % 3] = dis[u.first][u.second] + 1;
				que.push({v, (u.second + 1) % 3});
			}
		}
	}
}

int main() {
	n = read(), m = read();
	while (m--) {
		int u = read(), v = read();
		G[u].push_back(v);
	}
	s = read(), t = read();
	bfs();
	if (dis[t][0] == -1) puts("-1");
	else printf("%d\n", dis[t][0] / 3);
	return 0;
}

Measured memory_bytes: 6912
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<deque>
#include<regex>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>

#define rep(i, n) for(int i=0;i<n;i++)

typedef int long long ll;
using namespace std;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const ll MOD = 1e9 + 7;
static const int MAX = 100;
static const int INF = (1 << 23);
int h,w;

char masu[1000][1000];



int main() {
    cin>>h>>w;
    vector<pair<int,int>> v;
    rep(i,h){
        rep(j,w){
            cin>>masu[i][j];
            if(masu[i][j]=='#'){
                v.push_back({i,j});
            }
        }
    }
    int ans=0;

    while(true) {
        bool t=1;
        vector<pair<int,int>> ne;

        for (int i = 0; i < v.size(); i++) {
            int a=v[i].first;int b=v[i].second;

            if(a+1<h&&masu[a+1][b]=='.') {
                masu[a + 1][b] = '#';
                t=0;
                if ((a+2<h&&masu[a + 2][b] == '.') || (b-1>=0&&masu[a + 1][b - 1] == '.')||( b+1<w&&masu[a + 1][b + 1] == '.')) {
                    ne.push_back({a + 1, b});

                }
            }
            if(a-1>=0&&masu[a-1][b]=='.'){
                masu[a-1][b]='#';
                t=0;
                if((masu[a-2][b]=='.'&&a-2>=0)||(masu[a-1][b-1]=='.'&&b-1>=0)||(masu[a-1][b+1]=='.'&&b+1<w)){
                    ne.push_back({a-1,b});

                }
            }
                if(b+1<w&&masu[a][b+1]=='.'){
                    masu[a][b+1]='#';
                    t=0;
                    if((masu[a][b+2]=='.'&&b+2<w)||(masu[a-1][b+1]=='.'&&a-1>=0)||(masu[a+1][b+1]=='.'&&a+1<h)){
                        ne.push_back({a,b+1});

                    }
                }
            if(b-1>=0&&masu[a][b-1]=='.'){
                masu[a][b-1]='#';
                t=0;
                if((masu[a][b-2]=='.'&&b-2>=0)||(masu[a+1][b-1]=='.'&&a+1<h)||(masu[a+1][b-1]=='.'&&a+1<h)){
                    ne.push_back({a,b-1});

                }
            }
        }

        /*rep(i,h){
        rep(j,w){
            cout<<masu[i][j];
        }
        cout<<endl;
    }*/
    //cout<<t<<endl;


        v=ne;

        if(t==1)break;
        else{
            ans++;
        }

    }
    /*rep(i,h){
        rep(j,w){
            cout<<masu[i][j]<<endl;
        }
    }*/

    cout<<ans<<endl;



    return 0;
}


Measured memory_bytes: 13420
/*  -*- coding: utf-8 -*-
 *
 * b.cc: B: Palindrome-phobia
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>

using namespace std;

/* constant */

/* typedef */

/* global variables */

int cns[3];

/* subroutines */

/* main */

int main() {
  string s;
  cin >> s;

  for (int i = 0; i < s.size(); i++) cns[s[i] - 'a']++;
  //for (int i = 0; i < 3; i++) printf("%d ", cns[i]); putchar('\n');

  int minc = cns[0], maxc = cns[0];
  for (int i = 1; i < 3; i++) {
    if (minc > cns[i]) minc = cns[i];
    if (maxc < cns[i]) maxc = cns[i];
  }

  if (maxc <= minc + 1) puts("YES");
  else puts("NO");
  return 0;
}


Measured memory_bytes: 512
realize50::Int->Int->Int
realize50 lim50 n = if mod n 50 == 0 && div n 50 <= lim50 then 1 else 0

realize100::Int->Int->Int->Int
realize100 lim50 lim100 n = sum [realize50 lim50 (n-(100*i))|i<-[0..min lim100 (div n 100)]]

realize500::Int->Int->Int->Int->Int
realize500 lim50 lim100 lim500 n = sum [realize100 lim50 lim100 (n-(500*i))|i<-[0..min lim500 (div n 500)]]


main::IO()
main=do
  ac<-getLine
  bc<-getLine
  cc<-getLine
  xc<-getLine
  let a:b:c:x:[]=map read [ac,bc,cc,xc]::[Int]
  print (realize500 c b a x)

Measured memory_bytes: 508
# https://atcoder.jp/contests/abc131/tasks/abc131_d

import itertools
from collections import Counter
from collections import defaultdict
import bisect
from heapq import heappush, heappop

def main():
    N = int(input())
    AB = []
    for _ in range(N):
        a, b = map(int, input().split())
        AB.append((a, b))

    AB.sort(key=lambda x: x[1])

    possible = True
    current = 0
    for a, b in AB:
        current += a
        if current <= b:
            pass
        else:
            possible = False
            break

    print('Yes' if possible else 'No')


if __name__ == '__main__':
    main()


Measured memory_bytes: 75992
#include<iostream>
#include <bits/stdc++.h>
#include<string>
#include<algorithm>
#include <utility>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)


int main(){
    int N, sum, summin=100100100;
    cin >> N;
    int X[N];
    rep(i,N) cin >> X[i];

    for (int p =1; p < 101;p++){
        sum =0;
        rep(i,N){
            sum += (X[i]-p)*(X[i]-p);
        }
        if(sum < summin) summin = sum;
    }
    cout << summin << endl;
}

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

int main() {
  long long int h, w;
  cin >> h >> w;
  if(h % 3 == 0 || w % 3 == 0) {
    cout << 0 << endl;
    return 0;
  }

  double area = (double)(h * w) / 3;
  // candidate1
  long long int ans1 = 0;
  long long int hh = round(area / w);
  if(w % 2 == 0) ans1 = abs(hh * w - (h - hh) * w / 2);
  else {
    vector<long long int> vec = {hh * w, (h - hh) * (w / 2), (h - hh) * (w / 2 + 1)};
    sort(vec.begin(), vec.end());
    ans1 = vec[2] - vec[0];
  }

  // candidate2
  long long int ans2 = 0;
  long long int ww = round(area / h);
  if(h % 2 == 0) ans2 = abs(ww * h - (w - ww) * h / 2);
  else {
    vector<long long int> vec = {ww * h, (w - ww) * (h / 2), (w - ww) * (h / 2 + 1)};
    sort(vec.begin(), vec.end());
    ans2 = vec[2] - vec[0];
  }

  vector<long long int> ans = {ans1, ans2, h, w};

  cout << *min_element(ans.begin(), ans.end()) << endl;
}

Measured memory_bytes: 512
def solve():
    H,W,M = map(int,input().split())
    h_counter = [0] * H
    w_counter = [0] * W

    opponents = []
    for _ in range(M):
        h, w = map(lambda x:int(x)-1, input().split())
        h_counter[h] += 1
        w_counter[w] += 1
        opponents.append((h,w))
    
    h_max = max(h_counter)
    w_max = max(w_counter)

    h_max_area_cnt = 0
    h_max_area_nums = set()
    for h in range(H):
        if h_counter[h] == h_max:
            h_max_area_nums.add(h)
            h_max_area_cnt += 1

    w_max_area_cnt = 0
    w_max_area_nums = set()
    for w in range(W):
        if w_counter[w] == w_max:
            w_max_area_nums.add(w)
            w_max_area_cnt += 1

    max_area_cnt = h_max_area_cnt * w_max_area_cnt

    opponent_in_max_area = 0
    for h,w in opponents:
        if h in h_max_area_nums and w in w_max_area_nums:
            opponent_in_max_area += 1

    if max_area_cnt > opponent_in_max_area:
        print(h_max + w_max)
    else:
        print(h_max + w_max - 1)

if __name__ == '__main__':
    solve()


Measured memory_bytes: 205356
n, m = map(int,input().split())
a = [int(input()) for i in range(m)]
dp = [float("inf")] * (n+1)
dp[0] = 1
dp[1] = 1
for i in a:
    dp[i] = 0
for i in range(2, n+1):
    dp[i] = min(dp[i], (dp[i-1] + dp[i-2]))
print(dp[n] % 1000000007)

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

typedef long long ll;
typedef long double ld;
typedef vector<vector<int>> Graph;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
#define pi 3.14159265359
#define inf 2147483647
#define INF 9223372036854775807
#define mod 1000000007
#define mod2 998244353

int bfs(const vector<vector<char>> &v, int x, int y) {//点(x, y)をスタートに、一番遠い'.'までの距離を求める
    int h = v.size(), w = v[0].size();
    vector<vector<int>> dist(h, vector<int>(w, -1));
    dist[x][y] = 0;
    int res = 0;
    queue<pair<int, int>> que;
    que.push(make_pair(x, y));
    while(!que.empty()) {
        pair<int, int> current = que.front();
        int x = current.first, y = current.second;
        res = max(res, dist[x][y]);
        que.pop();
        for(int i = 0; i < 4; i++) {
            int nextx = x + dx[i];
            int nexty = y + dy[i];
            if(nextx < 0 || nextx >= h || nexty < 0 || nexty >= w) continue;
            if(v[nextx][nexty] == '#') continue;
            if(dist[nextx][nexty] == -1) {
                que.push(make_pair(nextx, nexty));
                dist[nextx][nexty] = dist[x][y] + 1;
            }
        }
    }
    return res;
}

int main() {
    int H, W; cin >> H >> W;
    vector<vector<char>> S(H, vector<char>(W));
    for(int i = 0; i < H; i++) for(int j = 0; j < W; j++) cin >> S[i][j];
    int ans = 0;
    for(int i = 0; i < H; i++) for(int j = 0; j < W; j++) {
        if(S[i][j] == '.') {
        int cnt = bfs(S, i, j);
        ans = max(ans, cnt);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3668
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ins insert
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
ll modfac(ll a){
    ll ans=1;
    while(a>1){
        ans*=a;
        ans%=1000000007;
        a--;
    }
    return ans;
}
ll modinv(ll a,ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
}
struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) {}

    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};
ll modpow(ll a, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
int main(){
    ll n,k;cin >> n >> k;
    vl v(n);
    rep(i,n)cin >> v[i];
    ll ans=0;
    rep(i,n-1){
        if(v[i]+v[i+1]>k){
            ll a=v[i]+v[i+1];
            v[i+1]=max((ll)0,k-v[i]);
            v[i]=k-v[i+1];
            ans+=a-v[i]-v[i+1];
        }
    }
    cout << ans <<endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
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;}
using ll = long long;

ll n,m,k,a,b;
string s,t;

int main() {
  cin >> s;
  cout << (s[1]=='B' ? "ARC" : "ABC") << endl;
}

Measured memory_bytes: 3620
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author gainullin.ildar
 */

#include <bits/stdc++.h>

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>

using namespace std;

typedef long long ll;

const int N = 1e5 + 7;

int n;
int h[N];
ll w[N];
int A, B;

bool check(ll x)
{
    for (int i = 0; i < n; i++)
    {
        w[i] = h[i];
    }
    for (int i = 0; i < n; i++)
    {
        w[i] -= x * (ll) B;
    }
    for (int i = 0; i < n; i++)
    {
        if (w[i] <= 0)
        {
            continue;
        }
        else
        {
            int need = w[i] / (A - B) + bool(w[i] % (A - B));
            x -= need;
        }
    }
    return (x >= 0);
}

class TaskD
{
public:
    void solve(std::istream &in, std::ostream &out)
    {
        in >> n >> A >> B;
        for (int i = 0; i < n; i++)
        {
            in >> h[i];
        }
        sort(h, h + n);
        reverse(h, h + n);
        int l = -1, r = 1e9 + 7;
        while (l < r - 1)
        {
            int m = (l + r) / 2;
            if (check(m))
            {
                r = m;
            }
            else
            {
                l = m;
            }
        }
        out << r << '\n';
    }
};


int main()
{
    ios::sync_with_stdio(0);
    TaskD solver;
    std::istream &in(std::cin);
    std::ostream &out(std::cout);
    solver.solve(in, out);
    return 0;
}


Measured memory_bytes: 1408
a = raw_input()
# SUN, MON, TUE, WED, THU, FRI, or SAT
if a == "SUN":
  r = 7
if a == "MON":
  r = 6
if a == "TUE":
  r = 5
if a == "WED":
  r = 4
if a == "THU":
  r = 3
if a == "FRI":
  r = 2
if a == "SAT":
  r = 1
print(r)

Measured memory_bytes: 2568
from operator import itemgetter

N, M = map(int, input().split(" "))
A = list(map(int, input().split(" ")))
BC = [list(map(int, input().split(" "))) for _ in range(M)]

A = sorted(A)
BC = sorted(BC, key=itemgetter(1), reverse=True)
now = 0
count = 0
flag = False

for b, c in BC:
    while True:
        # print(A[now], c)
        if A[now] >= c:
            flag = True
            break
        count += c-A[now]
        b -= 1
        now += 1
        if now >= N:
            flag = True
            break
        if b <= 0:
            break
    if flag:
        break
print(sum(A) + count)


Measured memory_bytes: 33740
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N;
int min_a = (int)1e+9;
int max_a = 0;
vector<int> A;

int main(void) {
	cin >> N;

	A.resize(N);
	for (int i = 0; i < N; ++i) {
		cin >> A[i];
		if (A[i] < min_a) min_a = A[i];
		if (A[i] > max_a) max_a = A[i];
	}
	if (max_a - min_a > 1) {
		cout << "No\n";
		return 0;
	}
	if (max_a - min_a == 0) {
		if ((max_a == N - 1) || (2 * max_a <= N))
			cout << "Yes\n";
		else
			cout << "No\n";
		return 0;
	}
	sort(A.begin(), A.end());
	vector<int>::iterator itr = lower_bound(A.begin(), A.end(), max_a);
	int x = distance(A.begin(), itr);
	int y = N - x;
	if ((x < max_a) && (2 * (max_a - x) <= y))
		cout << "Yes\n";
	else
		cout << "No\n";

	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[202020];
int n;
ll ans,cnt;
int main(){
    scanf("%s",s);
    n=strlen(s);
    for(int i=0;i<n;i++){
        if(s[i] == 'B') cnt++;
        else ans+=cnt;
    }
    printf("%lld",ans);
}


Measured memory_bytes: 384