akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;using ll=long long;using uint=unsigned int;using pii=pair<int,int>;using pll=pair<ll,ll>;using ull = unsigned long long;using ld=long double;template<typename T>void _(const char*s,T h){cerr<<s<<" = "<<h<<"\n";}template<typename T,typename...Ts>void _(const char*s,T h,Ts...t){int b=0;while(((b+=*s=='(')-=*s==')')!=0||*s!=',')cerr<<*s++;cerr<<" = "<<h<<",";_(s+1,t...);}// break continue pop_back 998244353
#define int ll
#define pii pll
#define f first
#define s second
#define pb emplace_back
#define forn(i,n) for(int i=0;i<(n);++i)
#define sz(a)((int)(a).size())
#define sqr(x) ((x)*(x))
struct init{init(){cin.tie(0);iostream::sync_with_stdio(0);cout<<fixed<<setprecision(10);cerr<<fixed<<setprecision(5);}~init(){
#ifdef LOCAL
#define dbg(...) _(#__VA_ARGS__,__VA_ARGS__)
cerr<<"Time elapsed: "<<(double)clock()/CLOCKS_PER_SEC<<"s.\n";
#else
#define dbg(...) 
#endif
}}init;template<typename T,typename U>void upx(T&x,U y){if(x<y)x=y;}template<typename T,typename U>void upn(T&x,U y){if(x>y)x=y;}mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());const int D=4,dx[]={+1,0,-1,0},dy[]={0,+1,0,-1};
const int N=505050;
int dp[N][4];//ostalos 0,1,vse krome 1,vse
int get(const vector<int>&a,int i,int j){
    if(j<2)return j;
    if(j==2)return a[i]-1;
    return a[i];
}
int solve(const vector<int>&a){
    if(a.empty())return 0;
    int n=sz(a);
    dp[0][0]=-N;
    dp[0][1]=(a[0]==1?0:-N);
    dp[0][2]=-N;
    dp[0][3]=0;
    for(int i=1;i<n;++i){
        forn(j,4)dp[i][j]=-N;
        forn(j,4)if(get(a,i-1,j))upx(dp[i][0],dp[i-1][j]+a[i]);
        forn(j,4)if(get(a,i-1,j))upx(dp[i][1],dp[i-1][j]+a[i]-1);
        forn(j,4)upx(dp[i][2],dp[i-1][j]+get(a,i-1,j));
        forn(j,4)upx(dp[i][3],dp[i-1][j]+0);
        forn(j,4)dbg(i,j,dp[i][j]);
    }
    int res=0;
    forn(i,4)upx(res,dp[n-1][i]);
    return res;
}
int32_t main(){

    int n;
    string s;
    cin>>n>>s;
    int c0=0,c1=0;
    vector<int> a;
    int ans=0;
    for(char c:s){
        if(c=='0'){
            if(c1>0){
                a.pb(c1);
                c1=0;
            }
            c0++;
            if(c0==2){
                ans+=solve(a);
                a.clear();
            }
        }else{
            c0=0;
            c1++;
        }
    }
    if(c1)a.pb(c1);
    ans+=solve(a);
    cout<<ans<<'\n';

    return 0;
}


Measured memory_bytes: 3932
#include <iostream>
#include <string>


int main() {
    int N;
    std::cin >> N;

    std::string S;
    std::cin >> S;

    int reverse_cnt = 0;
    for (int i = 0; i < N; i++) {
        if (S[i] == '.') reverse_cnt++;
    }

    int min_reverse_cnt = reverse_cnt;
    for (int i = 0; i < N; i++) {
        if (S[i] == '.') {
            reverse_cnt--;
            if (reverse_cnt < min_reverse_cnt) {
                min_reverse_cnt = reverse_cnt;
            }
        }
        if (S[i] == '#') {
            reverse_cnt++;
        }
    }
    std::cout << min_reverse_cnt << std::endl;
}


Measured memory_bytes: 644
import java.util.Scanner;

public class Main{
	public static void main(String[] args)
	{
		Scanner sc =new Scanner(System.in);
		String a=sc.next();
		String ans;

		if (a.equals("a") || a.equals("o") || a.equals("i") || a.equals("e") || a.equals("u")) ans="vowel";
		else ans="consonant";
		
		System.out.println(ans);	
	}
	
} 

Measured memory_bytes: 21844
#include <iostream>
#include <vector>
#include <string>
#include <functional>
using namespace std;

int main(int argc, char *argv[])
{
  string t, p;
  cin >> t >> p;

  int n = t.size();
  int m = p.size();
  
  vector<int> ks;
  int k = 0;
  int i = 0;
  while(k < n) {
    while(k < n && t[k] != p[i]) k++;
    if(k >= n) break;
    ks.push_back(k);
    k++;
    i++;
    if(i == m) break;
  }
  if(i < m) { // no match
    cout << "no" << endl;
    return 0;
  }
  // now, found a match. let's try next!
  // try moving the last one to the next position
  // if possible, then the second match found.
  // if not, try moving the 2nd last one to the next position before the last,
  // and so on.
  ks.push_back(n);
  while(i > 0) {
    i--;
    for(k = ks[i] + 1; k < ks[i+1]; k++) {
      if(t[k] == p[i]) { // the second match!
        cout << "no" << endl;
        return 0;
      }
    }
  }
  cout << "yes" << endl;
}

Measured memory_bytes: 6112
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
using namespace std;
#define rep(i,a,n) for(ll i=a;i<n;i++)
#define rrep(i,a,n) for(ll i=n;i>=a;i--)
typedef long long ll;
typedef pair<ll,ll> P;
const ll INF = 1e+17;
const ll MODcdf = 998244353;
string keyence="keyence";
ll k,n;
ll t[100000],d[100000];
int main(){
    ll n,a,b;cin>>n>>a>>b;
    ll ma=min(a,b);
    ll mi=a+b-n;
    if(mi<0)mi=0;
    cout<<ma<<" "<<mi<<endl;
}

Measured memory_bytes: 256
#include<cstdio>
int a[200000];
int main()
{
	int n,c=0,i;long long d=0;
	scanf("%d",&n);
	for(i=0;i<n;i++)
		scanf("%d",a+i);
	for(i=n;i--;c&&c--)
		if(a[i]<c||a[i]>i)return puts("-1"),0;
		else if(a[i]>c)d+=c=a[i];
	printf("%lld\n",d);
}

Measured memory_bytes: 896
#include <iostream>

using namespace std;
long long n;
int x,i,o,p;
int main()
{
    cin>>n>>p;
    for(i=1;i<=n;i++)
    {
        cin>>x;
        o|=x;
    }
    o%=2;
    if(o==1)
    {
        cout<<(1LL<<(n-1));
    }
    else
    {
        if(p==0) cout<<(1LL<<n);
        else cout<<'0';
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void)
{
	ios_base::sync_with_stdio(false);
	int A[10001]={};
	int n,num;
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> num;
		A[num]+=1; 
	}
	for(int i=0;i<n;i++){
		if(0<A[i]){
			cout << i;
			A[i]-=1;
			break;
		}
	}
	for(int i=0;i<10001;i++){
		if(0<A[i]){
			cout << " " << i;
			A[i]-=1;
			i--;
		}
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 1248
#include<bits/stdc++.h>
using namespace std;
int main()
{
  long long  n, k, a, x;
  cin >> n >> k;

  if(k <= n){
    a =n%k;
    x = min(a, k-a);
  }else{
    x = min(k-n, n);
  }
  
  cout << x <<endl;
}



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

int main() {

	string a;

	cin >> a;

	int cou = 0;

	for (int i = 0;i < 3;i++) {
		if (a[i] == '1') {
			cou++;
		}
	}

	cout << cou << endl;

	return 0;
}

Measured memory_bytes: 256
n, m = map(int, input().split())
sc = [input().split() for _ in range(m)]
sc = list(map(list, set(map(tuple, sc))))
sc.sort()

if n < len(sc):
  print("-1")
  exit()
else:
  for i in range(len(sc)-1):
    if sc[i][0] == sc[i+1][0]:
      print("-1")
      exit()
      
for i in range(len(sc)):
  if n != 1 and int(sc[i][0]) == 1 and int(sc[i][1]) == 0:
    print("-1")
    exit()
    

if len(sc) == 0:
  if n == 1:
    print("0")
    exit()
  elif n == 2:
    print("10")
    exit()
  else:
    print("100")
    exit()

ans = 0

if n == 2 and len(sc) == 1:
  if int(sc[0][0]) == 2:
    ans += 10

if n == 3 and len(sc) == 1:
  if int(sc[0][0]) != 1:
    ans += 100

if n == 3 and len(sc) == 2:
  if int(sc[0][0]) != 1 and int(sc[1][0]) != 1:
    ans += 100

for i in range(len(sc)):
  k = int(sc[i][0])
  ans += int(sc[i][1]) * (10 ** (n-k))

print(ans)

Measured memory_bytes: 38384
#include <iostream>

using namespace std;

int main(){
  unsigned int N;
  cin >> N;
  int *C = new int[N];
  int *S = new int[N];
  int *F = new int[N];

  unsigned int i;
  for(i = 0; i < N-1; i++){
    cin >> C[i] >> S[i] >> F[i];
  }

  for(i = 0; i < N-1; i++){
    unsigned int j;
    int time = 0;
    for(j = i; j < N-1; j++){
      if(time <= S[j]){
        time = S[j] + C[j];
      }else{
        if((time - S[j])%F[j] == 0){
          time += C[j];
        }else{
          time = ((time - S[j]) / F[j] + 1) * F[j] + S[j] + C[j];
        }
      }
    }

    cout << time << endl;
  }
  cout << "0" << endl;

  delete[] C;
  delete[] S;
  delete[] F;
}


Measured memory_bytes: 256
import std.stdio;
import std.string;
import std.conv;
import std.range;
import std.array;
import std.algorithm;
import std.typecons;
import std.math;

void main() {
	while(true) {
		string[] cin;
		cin=split(readln());
		int n=to!int(cin[0]),m=to!int(cin[1]);
		if(n==0 && m==0) break;
		int x=-1,y=-1,min=1000000000,sum1=0,sum2=0;
		int[] a=new int[n],b=new int[m];
		for(int i=0; i<n; i++) {
			cin=split(readln());
			a[i]=to!int(cin[0]);
			sum1+=a[i];
		}
		for(int i=0; i<m; i++) {
			cin=split(readln());
			b[i]=to!int(cin[0]);
			sum2+=b[i];
		}
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(sum1-a[i]+b[j]==sum2-b[j]+a[i]) {
					if(min>a[i]+b[j]) {
						x=a[i];
						y=b[j];
						min=x+y;
					}
				}
			}
		}
		if(x==-1) writeln(-1);
		else writefln("%d %d",x,y);
	}
}


Measured memory_bytes: 1068
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <functional>
#include <vector>
#include <list>
#include <map>
#include <stack>
#include <queue>
using namespace std;
#define sz size()
#define rep(i,a,n) for(ll i = (a);i < (n);i++)
typedef long long ll;
#define print(x) cout << (x) << endl;

ll n,m,c,r;

int main(){
    while(cin >> n >> m >> c >> r, (n+m+c+r)){
        ll ans = 0;

        if(n < c*m){
            double p = (double)(c*m-n)/r;
            double q = p - (int)p;
            if(q != 0)ans++;
            ans += p;
        }

        print(ans);
    }
    return 0;
}




Measured memory_bytes: 3084
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n,x,f=0;
  cin >> n;
  while(n!=0)
  {
    x = n % 10;
    n = n / 10;
    if(x == 7)
    { f=1;  }
  }
  if(f==1) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 3644
//AtCoder ABC102 C - Linear Approximation
#include <bits/stdc++.h>
using namespace std;
using ll=int64_t;
ll BinarySearch(ll low, ll high, std::function<bool(ll)> check){
    if(high-low==1){
        return low;
    }
    ll mid = (high+low)/2; 
    if(check(mid)){
        return BinarySearch(mid, high, check);
    }else{
        return BinarySearch(low, mid, check);
    }
}
int main() {
#if LOCAL&0
    std::ifstream in("./test/sample-3.in");
    std::cin.rdbuf(in.rdbuf());
#endif
    ll N; cin>>N;
    vector<ll> an(N+1,0);
    vector<ll> bn(N+1,0);
    ll minv=INT64_MAX,maxv=0;
    for(ll i=1;i<=N;++i){
        ll a; cin>>a;
        an[i]=a;
        bn[i]=a-i;
        minv=min(a,minv);
        maxv=max(a,maxv);
    }
    sort(bn.begin()+1,bn.end()); //0は未使用なので
    auto calca = [&](ll b){
        ll ret=0;
        for(ll i=1;i<=N;++i){
            ret += abs(an[i]-(b+i));
        }
        return ret;
    };
    auto calcb = [&](ll b){
        ll ret=0;
        for(ll i=1;i<=N;++i){
            ret += abs(bn[i]-b);
        }
        return ret;
    };
#if LOCAL&0
    //test
    ll tmp=INT64_MAX;
    for(ll i=bn[0];i<=bn.back();++i){
        auto t=calcb(i);
        tmp=min(tmp,t);
        cout<<i<<","<<tmp<<endl;
    }
    cout<<tmp<<endl;
#endif
    ll ans=INT64_MAX;
    ans=min(calcb(bn[N/2]),ans);
    ans=min(calcb(bn[N/2+1]),ans);
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3328
#include<bits/stdc++.h>
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>*/
 
using namespace std;
//using namespace __gnu_pbds;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define int long long 
#define rep(i,n) for(int i=0;i<n;i++)
#define repa(i,arr,n) for(int i=arr;i<=n;i++)
#define repd(i,arr,n) for(int i=arr;i>=n;i--)
#define trav(arr,x) for(auto& arr:x)
#define all(c) c.begin(), c.end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define sz(arr) arr.size()
#define pi 3.14159265358979323846
#define MAX 500003
#define vi vector<int>
#define pii pair<int,int>
#define pqueue priority_queue<int>
#define pdqueue priority_queue<int,vi,greater<int> >
//#define endl "\n"
 
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
 
const int mod=998244353;
int power(int a,int b)
{
    int ans=1;
    while(b)
    {
        if(b&1)
        {
            ans=(ans*a);
        }
        a=(a*a);
        b>>=1;
    }
    return ans;
}

int32_t main()
{
    fast;
    int t,cnt1=0,cnt2=0,cnt3=0,cnt4=0;
    cin>>t;
    while(t--)
    {
        string str;
        cin>>str;

        if(str=="AC") cnt1++;
        else if(str=="WA") cnt2++;
        else if(str=="TLE") cnt3++;
        else cnt4++;
    }

    cout<<"AC x "<<cnt1<<endl;
    cout<<"WA x "<<cnt2<<endl;
    cout<<"TLE x "<<cnt3<<endl;
    cout<<"RE x "<<cnt4<<endl;
}   


Measured memory_bytes: 3656
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout << (#x) << " is " << (x) << endl
#define debug cout << "hi" << endl

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

ll gcd(ll a, ll b) {return (!b ? a : gcd(b, a % b));}
bool cmp(pair<ll,ll>a,pair<ll,ll>b){return a.first>b.first;}

const ll mod = 1e9 + 7;
const int INF32 = 1<<30;
const ll INF64 = 1LL<<60;
const ld pi = 3.141592653589793;

vector< vector<int> >adj;
vector<int>ans;

void dfs(int v,int prev,int val){
     for(int i = 0;i<adj[v].size();i++){
        if(adj[v][i]==prev) continue;
        ans[adj[v][i]] += val;
        dfs(adj[v][i],v,ans[adj[v][i]]);
     }
}

void solve(){
     int n,m;cin >> n >> m;
     adj.resize(n+1);ans.resize(n+1);
     for(int i = 0;i<n-1;i++){
        int v,u;cin >> v >> u;
        adj[v].push_back(u);
        adj[u].push_back(v);
     }
     for(int i = 0;i<m;i++){
        int j,k;cin >> j >> k;
        ans[j] += k;
     }
     dfs(1,0,ans[1]);
     for(int i = 1;i<=n;i++) cout << ans[i] <<' ';
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    solve();
    return 0;
}


Measured memory_bytes: 27476
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
const ll MOD = 1e9+7;
const ll INF = 1e18;
ll dp[20010][300];

int main(){
  ll n,m;
  while(cin>>n>>m,n){
	ll c[22],x[20010];
	for(int i=0;i<m;i++)cin>>c[i];
	for(int i=0;i<n;i++)cin>>x[i];
  
	fill_n(*dp,20010*300,INF);

	dp[0][128]=0;
	for(int i=0;i<n;i++){
	  for(int j=0;j<256;j++){
		if(dp[i][j]==INF)continue;
		for(int k=0;k<m;k++){
		  int nj=j+c[k];
		  nj=min(nj,255);
		  nj=max(nj,0);
		  dp[i+1][nj]=min(dp[i+1][nj],dp[i][j]+(nj-x[i])*(nj-x[i]));
		}
	  }
	}

	ll ans=INF;
	for(int i=0;i<256;i++){
	  ans=min(ans,dp[n][i]);
	}
	cout<<ans<<endl;
  }
  return 0;
}



Measured memory_bytes: 50140
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll a[200001];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n; cin >> n;

    ll sum = 0;
    ll ans = 0;
    ll mod = 1e9 + 7;

    for(int i = 0; i < n; i++){
        cin >> a[i];
        sum += a[i];
        sum %= mod;
    }


    for(int i = 0; i < n ; i++){
        sum -= a[i];
        if(sum < 0)sum += mod;
        ans += a[i] * sum;
        if(ans < 0)sum += mod;
        ans %= mod;
    }
    cout << ans <<'\n';





}


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

int gcd(int a,int b) {
  if (a>b) {
    swap(a,b);
  }
  if (b%a == 0) {
    return a;
  }
  return gcd(b%a,a);
}

int main() {
  int A,B;
  cin >> A >> B;
  if (A < 6) {
    cout << 0 << endl;
    return 0;
  }
  else if (A < 13) {
    cout << B / 2 << endl;
    return 0;
  }
  else {
    cout << B << endl;
    return 0;
  }
  return 0;
}

Measured memory_bytes: 256
import numpy as np
def make_primes(U=55555):
    is_prime = np.zeros(U,np.bool)
    is_prime[2] = 1
    is_prime[3::2] = 1
    M = int(U**.5)+1
    for p in range(3,M,2):
        if is_prime[p]:
            is_prime[p*p::p+p] = 0
    return is_prime.nonzero()[0], is_prime
n = int(input())
a = []
primes, is_prime = make_primes()
for pi in primes:
    if pi % 5 == 1:
        a.append(pi)

print(' '.join(map(str, a[:n])))


Measured memory_bytes: 12632
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int maxn = 2e5 + 20;
ll a[maxn] , res;
int main()
{
    int n , t;
    cin >> n >> t;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
        res += t;
        if(!i)
            continue;
        if(a[i] >= a[i - 1] + t)
            res = res;
        else
            res -= t , res += a[i] - a[i - 1];
    }
    cout << res;
    return 0;
}


Measured memory_bytes: 1792
N = int(input())
# S = input()
A_list = list(map(int,input().split()))
# X2_list = [list(map(int,input().split())) for i in range(N)]
full_sum = sum(A_list)
min_haba = full_sum
tmp_sum = 0
for i in range(N):
    tmp_sum += A_list[i]
    min_haba = min(abs((full_sum - tmp_sum)- tmp_sum),min_haba)
    #print(min_haba)

print(min_haba)

Measured memory_bytes: 26024
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define repr(i,n) for(ll i=(n-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define br cout << "\n";
using namespace std;
const long long INF = 1e10;
const long long MOD = 1e9+7;
using Graph = vector<vector<ll>>;
using pll = pair<ll, ll>;
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;}

// 0 false, 1 true 
// string to int : -48
// a to A : -32
// ceil(a)  1.2->2.0
// c++17	g++ -std=c++17 a.cpp

int main() {
    std::cout << std::fixed << std::setprecision(15);
    vector<long long> vec(5);
    for(long long i = 0; i < 5; i ++){
        cin >> vec[i];
    }

    rep(i, 5){
        if(vec[i] == 0){
            cout << i+1 << endl;
        }
    }


}

Measured memory_bytes: 3588
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
#include<complex>
using namespace std;

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (1e+18) + 7;
typedef pair<int, int>P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-6;
const ld pi = acos(-1.0);
//typedef vector<vector<ll>> mat;
typedef vector<int> vec;

ll mod_pow(ll a, ll n) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a%mod;
		a = a * a%mod; n >>= 1;
	}
	return res;
}

struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 20;
modint fact[max_n], factinv[max_n];
void init() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}


int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int dp[10001];
void solve() {
	int h, n; cin >> h >> n;
	fill(dp, dp + h + 1, mod);
	dp[0] = 0;
	rep(i, n) {
		int a, b; cin >> a >> b;
		rep(j, h) {
			dp[min(j + a, h)] = min(dp[min(j + a, h)],dp[j] + b);
		}
	}
	cout << dp[h] << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//init();
	//int t; cin >> t; rep(i, t)solve();
	//while (cin >> n, n)solve();
	solve();
	stop
		return 0;
}


Measured memory_bytes: 16640
import math
import random

def fermat(k):
    if k % 2 == 0 and k != 2:
      return False
            
    if pow(2, k-1, k) == 1:
      return True
    else:
      return False
def is_prime(n):
    if n == 2: return True
    if n == 1 or n & 1 == 0: return False

    d = (n - 1) >> 1
    while d & 1 == 0:
        d >>= 1

    for k in range(100):
        a = random.randint(1, n - 1)
        t = d
        y = pow(a, t, n)

        while t != n - 1 and y != 1 and y != n - 1:
            y = (y * y) % n
            t <<= 1

        if y != n - 1 and t & 1 == 0:
            return False

    return True    
def using_sqrt(k):  
    factor = 0
        
    # 2以外の偶数は素数ではないので無視する
    if k % 2 == 0 and k != 2:
        return False
        
    # 繰り返しの上限を対象の平方根にする
    for divisor in range(2, math.floor(math.sqrt(k))+1):
        if k % divisor == 0:
            factor += 1
                
    if factor == 0:
        return True
    else:
        return False
            
 
  
n=int(input())
while True:
  if fermat(n):
    if using_sqrt(n):
      print(n)
      break
  if is_prime(n):
    if using_sqrt(n):
      print(n)
      break    
  n+=1

Measured memory_bytes: 3824
package main

import (
	"fmt"
)

func main() {
	var s string
	var ans int
	fmt.Scan(&s)
	l, r := 0, len(s)-1
	// 方針が立たなかったので解説を見た
	for l < r {
		if s[l] == s[r] {
			l++
			r--
		} else if s[l] == 'x' {
			l++
			ans++
		} else if s[r] == 'x' {
			r--
			ans++
		} else {
			ans = -1
			break
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 1280
N,M=map(int,input().split())
A = list(range(1,N//2+1))*2
if N&1:A+=[(N+1)//2]
d=[1]+[0]*(N+N)
for x in A:
  for i in range(N+1):
    d[i]%=M
    d[i+x]+=d[i]
print(sum(d[:N])%M)

Measured memory_bytes: 40940
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef vector<char> VC;
typedef vector<double> VD;
typedef vector<string> VS;
typedef vector<ll> VLL;
typedef vector<PLL> VP;
const static int INF = 1000000000;
const static int MOD = 1000000007;
const int dx[4]={1, 0, -1, 0};
const int dy[4]={0, 1, 0, -1};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define rep(i,n) for (ll i=0; i<(ll)(n); i++)
#define repd(i,n) for (ll i=n-1; i>=0; i--)
#define rept(i,m,n) for(ll i=m; i<n; i++)
#define stl_rep(itr, x) for (auto itr = x.begin(); itr != x.end(); ++itr)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define PF push_front
#define PB push_back
#define SORT(V) sort((V).begin(), (V).end())
#define RVERSE(V) reverse((V).begin(), (V).end())
#define paired make_pair
#define PRINT(V) for(auto v : (V)) cout << v << " "
//charを整数に
int ctoi(char c) { if (c >= '0' && c <= '9') { return c - '0'; } return 0; }
// 累積和 for (int i = 0; i < N; ++i) s[i+1] = s[i] + a[i]; 
void cum_sum(int N,vector<double> a, vector<double> &s){ for(int i=0; i<N; i++){ s[i+1]=s[i]+a[i];}}
//ユークリッドの控除法
ll gcd(ll a,ll b){
    if(b == 0) return a;
    return gcd(b,a%b);
}
//最小公倍数
ll lcm(ll a,ll b){
    ll g = gcd(a,b);
    return a / g * b; // Be careful not to overflow
}
//素数判定
bool is_prime(long long n) {
    if (n <= 1) return false;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p == 0) return false;
    }
    return true;
}
int getdigit(ll num){
    unsigned digit=0;
    while(num!=0){
        num /= 10;
        digit++;
    }
    return digit;
}
//空白文字も入力 getline(cin, S);
//桁数指定 setprecision

int main()
{
    ios::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0);
    ll N;
    cin >> N;
    if(N%1000==0){
        cout << 0 << endl;
        return 0;
    }
    cout << 1000-N%1000 << endl;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#ifdef _DEBUG_
  #define debug(...) printf(__VA_ARGS__)
#else
  #define debug(...) (void)0
#endif
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;

int dig_sum(ll x) {
  int res = 0;
  while (x) {
    res += x % 10;
    x /= 10;
  }
  return res;
}

int main() {
  ll N;
  cin >> N;
  int ans = dig_sum(N);
  for (ll t = 1; t <= 10 * N; t *= 10) {
    ll x = N / t * t - 1;
    ans = max(ans, dig_sum(x));
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
#define LL long long
using namespace std;

const int N=105;
int n;
int f[3][N];

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d",&f[1][i]);
	for(int i=1;i<=n;++i) scanf("%d",&f[2][i]);
	for(int i=1;i<=2;++i)
		for(int j=1;j<=n;++j) f[i][j]+=max(f[i-1][j],f[i][j-1]);
	cout<<f[2][n];
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <iomanip>
#include <cmath>
using namespace std;
typedef long long ll;
string direction = "RLUD";
int dx[4] = {1,-1,0,0},dy[4] = {0,0,1,-1};

int N;
int main(){
    cin >> N;
    vector<ll> X[4],Y[4];
    ll x,y; char c;
    for(int i=0;i<N;i++){
        cin >> x >> y >> c;
        x *= 2; y *= 2;
        int d = direction.find(c);
        X[d].push_back(x); Y[d].push_back(y);
    }
    vector<ll> xs,ys;
    for(int k=0;k<4;k++){//各方向のx,yの最大値、最小値を入れる
        if(X[k].size()){
            xs.push_back(*max_element(X[k].begin(),X[k].end()));
            xs.push_back(*min_element(X[k].begin(),X[k].end()));
            ys.push_back(*max_element(Y[k].begin(),Y[k].end()));
            ys.push_back(*min_element(Y[k].begin(),Y[k].end()));
        }
    }
    vector<ll> t;
    for(auto x1:xs) for(auto x2:xs){//最適解を達成する時刻を列挙
        ll d = abs(x1-x2);
        t.push_back(d); t.push_back(d/2);
    }
    for(auto y1:ys) for(auto y2:ys){
        ll d = abs(y1-y2);
        t.push_back(d); t.push_back(d/2);
    }
    sort(t.begin(),t.end());
    t.erase(unique(t.begin(),t.end()),t.end());
    ll inf = 1e9,ans = 1e18;
    for(auto d:t){//時刻の候補をすべて試す
        ll xmax = -inf,xmin = inf,ymax = -inf,ymin = inf;
        for(int k=0;k<4;k++) for(int i=0;i<X[k].size();i++){
            ll x = X[k][i]+dx[k]*d,y = Y[k][i]+dy[k]*d;
            xmax = max(xmax,x);
            xmin = min(xmin,x);
            ymax = max(ymax,y);
            ymin = min(ymin,y);
        }
        ans = min(ans,(xmax-xmin)*(ymax-ymin));
    }
    cout << fixed;
    cout << setprecision(10) << 1.0*ans/4 << endl;
}

Measured memory_bytes: 2256
#include <bits/stdc++.h>
#include <boost/multi_array.hpp>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define FOR(i, n) for (int i = 0; i < int(n); i++)
#define FOR1(i, m, n) for (int i = int(m); i < int(n); i++)
#define MAX(a, b) ((a) >= (b) ? (a) : (b))
#define MIN(a, b) ((a) <= (b) ? (a) : (b))

int main(int argc, char *argv[]) {
  int N, M, Q;
  cin >> N >> M >> Q;

  //boost::multi_array<int, 2> mat(boost::extents[N + 1][N + 1]);
  int mat[501][501] = {};

  FOR(i, M) {
    int L, R;
    cin >> L >> R;
    mat[L][R]++;
  }

  FOR(i, N + 1) {
    FOR(j, N) { mat[i][j + 1] += mat[i][j]; }
  }

  for (int i = N; i > 0; i--) {
    FOR(j, N + 1) { mat[i - 1][j] += mat[i][j]; }
  }

  while (Q--) {
    int p, q;
    cin >> p >> q;
    cout << mat[p][q] << "\n";
  }

  return 0;
}


Measured memory_bytes: 1920
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;

int n, a, b, c, d;
int x[N];
bool valid;
string s;

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> a >> b >> c >> d;
    cin >> s;
    for(int i = 0; i < s.size(); i++) {
        if(s[i] == '#') x[i + 1] = 2;
        else x[i + 1] = 1;
    }
    valid = true;
    for(int i = a; i < c; i++) {
        if(x[i] == 2 && x[i + 1] == 2) valid = false;
    }
    for(int i = b; i < d; i++) {
        if(x[i] == 2 && x[i + 1] == 2) valid = false;
    }
    if(!valid) cout << "No\n";
    else if(c < d) cout << "Yes\n";
    else {
        valid = false;
        for(int i = b - 1; i < d; i++) {
            if(x[i] == 1 && x[i + 1] == 1 && x[i + 2] == 1) valid = true;
        }
        if(valid) cout << "Yes\n";
        else cout << "No\n";
    }
}

Measured memory_bytes: 4492
#include <iostream>
#include <map>
#include <string>

using namespace std;

int main()
{
    int n;
    cin >> n;
    std::map<std::string, int> mp;
    std::string s[n];
    int maxcnt = 0;
    for(int i=0; i<n; i++){
        cin >> s[i];
        mp[s[i]]++;
        if(mp[s[i]] > maxcnt){
            maxcnt = mp[s[i]];
        }
    }
    std::map<std::string, int>::iterator itr = mp.begin();
    while(itr != mp.end()){
        int tmp = itr->second;
        if(tmp == maxcnt){
            cout << itr->first << endl;
        }
        ++itr;
    }
        

    return 0;
}

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

const int P = 1e9 + 7;
const int N = 110000;

int modExp(int a, int n, int p) {
	int ret = 1;
	for (; n; n >>= 1, a = 1LL * a * a % p) if (n & 1) ret = 1LL * ret * a % p;
	return ret;
}

long long ret;

int dp[N], pw[N], qw[N];
map<int, int> H;

long long sum;

vector<int> adj[N];

void dfs(int u, int p) {
	dp[u] = dp[p] + 1;
	ret = (ret + pw[dp[u]]) % P;
	int ans = (P - ret) % P;
	for (int v : adj[u]) {
		if (v == p) continue;
		dfs(v, u);
	}
	ans = (ans + ret) * 1LL * qw[dp[u]] % P;
	sum += H[ans];
	H[ans]++;
}

int main() {
	ios_base::sync_with_stdio(0);
	int n; cin >> n;
	for (int i = 0; i <= n; i++) pw[i] = (i == 0 ? 1 : pw[i - 1] * 1LL * 999983) % P;
	for (int i = 0; i <= n; i++) qw[i] = modExp(pw[i], P - 2, P);
	for (int i = 1; i < n; i++) {
		int u, v; cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dp[0] = -1;
	dfs(1, 0);
	cout << sum << endl;
	return 0;
}



Measured memory_bytes: 22608
#include "bits/stdc++.h"

typedef long long int lli;

using namespace std;

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

	string s;
	cin >> s;
	lli ans = 0, cur = 0;
	for (int i = 0; i < s.size()-1; i++) {
		if (s[i] == 'A') { cur++; }
		else {
			if (s[i] == 'B' && s[i + 1] == 'C') {
				ans += cur;
				i++;
			}
			else { cur = 0; }
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 720
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] A = new int[5];
        for (int i=0; i<5; i++) {
            A[i] = sc.nextInt();
        }
        int x_max = A[2] + A[4];
        int x_min = A[2] - A[4];
        int y_max = A[3] + A[4];
        int y_min = A[3] - A[4];

        if (x_max <= A[0] & x_min >= 0 & y_max <= A[1] & y_min >= 0)
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}


Measured memory_bytes: 26324
#include <bits/stdc++.h>
     
#define all(A) begin(A), end(A)
#define rall(A) rbegin(A), rend(A)
#define sz(A) int(A.size())
#define pb push_back
#define mp make_pair
     
using namespace std;
     
typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef vector <ll> vll;
     
int main () {
  ios::sync_with_stdio(false); cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector <string> grid(n);
  for (int i = 0; i < n; i++) {
    cin >> grid[i];
  }
  const int INF = 1e9;
  const vector <int> dr = {0, 1, -1, 0};
  const vector <int> dc = {1, 0, 0, -1};
  function <int(pii, pii)> bfs = [&] (pii s, pii t) -> int {
    queue <pii> Q;
    vector <vector <int>> dis(n, vector <int> (m, INF));
    Q.push(s);
    dis[s.first][s.second] = 0;
    while (not Q.empty()) {
      pii u = Q.front();
      Q.pop();
      for (int d = 0; d < 4; d++) {
        int nr = u.first + dr[d];
        int nc = u.second + dc[d];
        pii v(nr, nc);
        if (not (0 <= min(nr, nc) and nr < n and nc < m)) continue;
        if (dis[u.first][u.second] + 1 < dis[nr][nc] and grid[nr][nc] == '.') {
          dis[nr][nc] = dis[u.first][u.second] + 1;
          Q.push(v);
        }
      }
    }
    return dis[t.first][t.second];
  };
  int ans = 0;
  for (int r1 = 0; r1 < n; r1++) {
    for (int c1 = 0; c1 < m; c1++) {
      for (int r2 = 0; r2 < n; r2++) {
        for (int c2 = 0; c2 < m; c2++) {
          if (grid[r1][c1] == '.' and
              grid[r2][c2] == '.') {
            ans = max(ans, bfs(pii(r1, c1), pii(r2, c2)));
          }
        }
      }
    }
  }
  cout << ans << '\n';
  return (0);
}


Measured memory_bytes: 256
#include<queue>
#include<stack>
#include<math.h>
#include<cmath>
#include<bitset>
#include<stdio.h>
#include<string>
#include<map>
#include<algorithm>
#include<vector>
#include<iostream>
#include<utility>
#include<functional>
#include<deque>
#include<list>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int main(){
  int n;
  cin >> n;
  cout << n*n*n << endl;
  return 0;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>

#define loop(v, f, l) for(int v = (f), v##_ = (l); v < v##_; ++v)

using namespace std;

typedef long long int lint;
static inline int in(){ int x; scanf("%d", &x); return (x); }
static inline lint inl(){ lint x; scanf("%lld", &x); return (x); }

int dp[9][101];

void init();
void make_dp(int sum, int prevused, bool* used, int depth);

void init()
{
	bool used[10] = {false};
	make_dp(0, -1, used, 0);
}

void make_dp(int sum, int prevused, bool* used, int depth)
{
	if( depth == 9 )return;
	
	for(int i = prevused + 1; i < 10; i++)
	{
		if( !used[i] )
		{
			sum += i;
			used[i] = true;
			dp[depth][sum]++;
			make_dp(sum, i, used, depth + 1);
			used[i] = false;
			sum -= i;
		}
	}
}

int main()
{
	int n, s;
	init();

	while(true)
	{
		scanf("%d%d", &n, &s);
		if( n == 0 && s == 0 )break;
		printf("%d\n", dp[n - 1][s]);
	}
	return (0);
}

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

int main() {
  
  int N, A, B, C, D; cin >> N >> A >> B >> C >> D;
  
  string S; cin >> S;
  
  if (C < D) {
    
    for (int i = A; i < D - 1; i++) {
      if (S.at(i) == '#' && S.at(i + 1) == '#') {
        cout << "No" << endl; return 0;
      }
    }
    
    cout << "Yes" << endl;
    
  }
  else {
    
    bool flagOfSpace = false, flagOfRock = true;
    
    for (int i = B - 2; i < D - 1; i++) {
      if (S.at(i) == '.' && S.at(i + 1) == '.' && S.at(i + 2) == '.') {
        flagOfSpace = true;
      }
    }
    
    for (int i = A; i < C - 1; i++) {
      if (S.at(i) == '#' && S.at(i + 1) == '#') {
        flagOfRock = false;
      }
    }
    
    if (flagOfSpace && flagOfRock) cout << "Yes" << endl;
    
    else cout << "No" << endl;
    
  }
  
}

Measured memory_bytes: 3704
#include <iostream>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
using P = pair<int,int>;

int main() {
    int n;
    ll sum=0;
    cin>>n;
    for (int i=1; i<=n; i++) {
        if (i%3==0||i%5==0) {
            continue;
        }
        sum+=i;
    }
    cout<<sum<<endl;
}

Measured memory_bytes: 3596
n = int(input())
out = ''
for i in range(3,n+1):
    if i % 3 == 0:
        out += ' {0}'.format(i)
        continue
    elif i % 10 == 3:
        out += ' {0}'.format(i)
        continue
    n = i
    while n // 10:
        n = n // 10
        if n % 10 == 3:
            out += ' {0}'.format(i)
            n = 0
print(out)

Measured memory_bytes: 7644
#include<stdio.h>
#include<string.h>
int main(){
	char a[101];
	gets(a);
	int n=strlen(a),r=0,flag1=1,flag2=1,flag3=1;
	int b=(n-1)/2,c=(n+3)/2;
	while(n-1>r){
		if(a[n-1]!=a[r])flag3=0;
		n--;
    	r++;
	}
	r=0,n=strlen(a);
	while(b-1>r){
		if(a[r]!=a[b-1])flag1=0;
		b--;
    	r++;
	}
  	while(n>c){
  		if(a[c-1]!=a[n-1])flag2=0;
		n--;
    	c++;
  	}
  	if(flag1==1&&flag2==1&&flag3==1)printf("Yes");
  	else printf("No");
	return 0;
} 

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

typedef struct {
    int num;
    int pref;
    int year;
    int rank;
} City;

int main() {
    int n, m;
    int p[100000], y[100000];
    City city[100000];
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> p[i] >> y[i];
        city[i] = {i, p[i], y[i], 0};
    }

    sort(city, city + m, [](City a, City b) -> bool {
        if (a.pref < b.pref) return true;
        if (a.pref == b.pref && a.year < b.year) return true;
        return false;
    });

    int r = 1;
    for (int i = 0; i < m - 1; i++) {
        city[i].rank = r;
        r++;
        if (city[i + 1].pref != city[i].pref) r = 1;
    }
    city[m - 1].rank = r;

    sort(city, city + m, [](City a, City b) -> bool {
        return a.num < b.num;
    });

    for (int i = 0; i < m; i++) {
        string pStr = to_string(city[i].pref);
        while (pStr.length() != 6) pStr.insert(0, "0");
        string rStr = to_string(city[i].rank);
        while (rStr.length() != 6) rStr.insert(0, "0");
        cout << pStr << rStr << endl;
    }
}

Measured memory_bytes: 5988
import sys
input = sys.stdin.readline

m = int(input())
sum1 = 0
sumc = 0
ans = 0

for i in range(m):
    d,c = map(int,input().split())
    sum1 += d * c
    sumc += c

ans += sumc + (sum1 - 1) // 9 - 1

print(ans)


Measured memory_bytes: 40428
import java.io.*;
import java.util.*;
import java.lang.String;
import java.util.Arrays;

import static java.lang.Integer.*;

public class Main extends PrintWriter {
    Main() { super(System.out, true); }
    Scanner sc = new Scanner(System.in);
    public static void main(String[] $) {
        Main o = new Main(); o.main(); o.flush();
    }
    //took bsearch from Dukkha
    private static int binSearch(Integer[] arr, int number){
        int left=0,right=arr.length-1,mid=(left+right)/2,ind=0;
        while(left<=right){
            if(arr[mid]<=number){
                ind=mid+1;
                left=mid+1;
            }
            else
                right=mid-1;
            mid=(left+right)/2;
        }
        return ind;
    }

    void main() {

       int a = sc.nextInt();
       int b = sc.nextInt();
       int c = sc.nextInt();

       print(c + " " + a + " " + b);    

    }
}

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

const ll MOD = 1000000007;

 
vector<long long> fact, finv, inv;

long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
}

void nCk(ll n, ll b) {
  finv[0] = finv[1] = 1;
  for (int i = 2; i < b + 5; i++)
  {
    finv[i] = finv[i - 1] * modinv(i, MOD);
    finv[i] %= MOD;
  }
  return ;
}

ll hoge (ll x) {
  ll y = 2;
  ll z = x;
  ll ans = 1;
  while (z)
  {
    if (z & 1)
    {
      ans *= y;
      ans %= MOD;
    }
    y *= y;
    y %= MOD;
    z >>= 1;
  }
  ans--;
  ans %= MOD;
  return ans;
}

int main() {
  ll n, a, b;
  cin >> n >> a >> b;

  ll ans = hoge(n);
  cerr << ans << endl;

  finv.resize(b + 5);
  nCk(n, b);
  ll comA = 1;
  for (int i = 0; i < a; i++)
  {
    comA *= (n - i);
    comA %= MOD;
  }
  ll comB = comA;
  comA *= finv[a];
  comA %= MOD;
  ans -= comA;
  if (ans < 0)
  {
    ans += MOD;
  }
  ans %= MOD;

  for (int i = a; i < b; i++)
  {
    comB *= (n - i);
    comB %= MOD;
  }
  comB *= finv[b];
  comB %= MOD;

  ans -= comB;
  if (ans < 0)
  {
    ans += MOD;
  }
  
  ans %= MOD;
  cout << ans << endl; 
  
  return 0;
}


Measured memory_bytes: 4756
#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
#include<math.h>
#include<bits/stdc++.h>
#define ll long long 
#define IOS ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mod 1000000009
using namespace std;
bool isprime(ll n)
{
    //if(n<2)
    //return false;
    if(n==1)
    return true;
    if(n==2 || n==3)
    return true;
    if(n%2==0)return false;
    for(ll i=3;i*i<=n;i+=2)
    {
        if(n%i==0)
        return false;
        
    }
    return true;
}
int gcd(ll a,ll b)
{
    if(a==0)
    return b;
    return gcd(b%a,a);
}
int lcm(ll a,ll b)
{
    return a*(b/gcd(a,b));
}
 set<ll> fac;
void allFactors(ll n)
{
   // set<ll> fac;
    for(ll i=1;i<=sqrt(n);i++)
    {
        if(n%i==0)
        {
            fac.insert(i);
            if(i!=n/i)
            {
                fac.insert(n/i);
               
            }
        }
    }
    //return fac.size();
}
bool threefactors(ll n)//when you have need of a no which is divisible by 1,itself,any other one no.
{
    ll p=sqrt(n);
    if(p*p==n)
    {
        if(isprime(p))
        return 1;
        else
        return 0;
    }
    else
    return 0;
}

int main()
{
     IOS
     //int w;
     //cin>>w;
     //while(w--)
     {
       int n,k;
       cin>>n>>k;
       int a[n+1];
       for(int i=1;i<=n;i++)
       {
           cin>>a[i];
       }
      ll dp[10000000];
      for(int i=0;i<10000000;i++)
      dp[i]=mod;
      dp[1]=0;
      for(int i=1;i<n;i++)
      {
          for(int j=i+1;j<=i+k;j++)
          {
              if(j<=n)
              dp[j]=min(dp[j],dp[i]+abs(a[i]-a[j]));
          }
      }
      cout<<dp[n];
     }
     return 0;
} 
//ascii of a=97
//ascii of A=65
//ascii of 0=48


Measured memory_bytes: 82160
#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

class UnionFind {
public:
  const static int MAX_N = 100010;
  int par[MAX_N];
  int rank[MAX_N];
  int s[MAX_N];
  bool used[MAX_N];
  UnionFind() { init(); }
  UnionFind(int n) { init(n); }
  void init() { for(int i=0; i<MAX_N; ++i) par[i] = i, rank[i] = 0, s[i] = 1; }
  void init(int n) { for(int i=0; i<n; ++i) par[i] = i, rank[i] = 0, s[i] = 1; }
  int find(int x) {
    if(par[x] == x) return x;
    return par[x] = find(par[x]);
  }
  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y) return;
    if(rank[x] < rank[y]) {
      par[x] = y; s[y] = s[x] + s[y];
    } else {
      par[y] = x; s[x] = s[x] + s[y];
      if( rank[x] == rank[y] ) rank[x]++;
    }
  }
  int size(int x) { return s[find(x)];}
  bool same(int x, int y) { return find(x) == find(y);}
  int group(int n) {
    REP(i, n) used[find(i)] = true;
    int ret = 0;
    REP(i, n) if(used[i]) ret++;
    return ret;
  }
};
UnionFind uf;

double x[105], y[105], z[105], r[105];
vector<pair<double, PII>> e;
signed main(void)
{
  while(true) {
    int n;
    cin >> n;
    if(!n) break;
    REP(i, n) cin >> x[i] >> y[i] >> z[i] >> r[i];

    e.clear();
    int m = 0;
    REP(i, n) FOR(j, i+1, n) {
      double d = sqrt((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) + (z[i]-z[j])*(z[i]-z[j])) - r[i] - r[j];
      if(d < 0) d = 0;
      e.PB({d, {i, j}});
      m++;
    }
    sort(ALL(e));

    uf.init();
    double ret = 0;
    for(auto i: e) {
      if(!uf.same(i.second.first, i.second.second)) {
        ret += i.first;
        uf.unite(i.second.first, i.second.second);
      }
    }
    cout << fixed << setprecision(3) << ret << endl;
  }

  return 0;
}

Measured memory_bytes: 5708
import java.util.*;
import java.io.*;
import java.nio.charset.StandardCharsets;

public class Main {
	public static void main(String[] args) throws IOException {
		InputStreamReader reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
		BufferedReader in = new BufferedReader(reader);
		String[] tokens = in.readLine().split(" ");
		int a = Integer.parseInt(tokens[0]);
		int b = Integer.parseInt(tokens[1]);
		if ((a + b) % 2 == 0) {
			System.out.println(((a + b) / 2));
		} else {
			System.out.println(((a + b) / 2 + 1));
		}
	}
}

Measured memory_bytes: 21332
#include <bits/stdc++.h>
#define MAX_N 128

using namespace std;

int s[MAX_N];

int main(void)
{
    int n;
    bool flag = false;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &s[i]);
        if (s[i] % 10) flag = true;
    }
    sort(s, s + n);
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += s[i];
    for (int i = 0; i < n; i++) {
        if (sum % 10 == 0) {
            if (s[i] % 10 == 0) continue;
            else sum -= s[i];
        }
        else break;
    }
    if (!flag) sum = 0;
    printf("%d\n", sum);
    return 0;
}


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

int main(){
    int N, K;
    cin >> N >> K;

    vector<int> p(N);
    REP(i, N) cin >> p[i];

    // 整数で扱う
    REP(i, N) p[i]++;

    int mx = 0;
    int s = 0;

    queue<int> q;
    REP(i, N){
        s += p[i];
        q.push(p[i]);
        if (q.size() > K) {
            s -= q.front();
            q.pop();
        }
        if (q.size() == K) {
            mx = max(mx, s);
        }
    }

    double ans = mx;
    ans /= 2;
    printf("%.10f\n", ans);
    return 0;
}

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

const int d[2] = {1, -1};
char s[4];
int a[4];

int main() {
    cin >> s;
    for (int i = 0; i < 4; i++)
        a[i] = s[i] - '0';
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                int t = a[0] + d[i] * a[1] + d[j] * a[2] + d[k] * a[3];
                if (t == 7) {
                    printf("%d%c%d%c%d%c%d=7\n", a[0], i==0?'+':'-', a[1], j==0?'+':'-', a[2], k==0?'+':'-', a[3]);
                    return 0;
                }
            }
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i,a,b) for(int i=(a); i<=(b); i++) 
#define rep(i,n); for(int i = 0; i < (n); i++)
#define chmin(a,b) if((a)>(b)) (a)=(b); 
#define chmax(a,b) if((a)<(b)) (a)=(b);
#define vi vector<int>
#define pi pair<int,int>
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define pf push_front
int gcd(int a,int b){/*a>=0,b>=0,￢(a=b=0)*/
  while(min(a,b)>0){if(a<b)swap(a,b);a%=b;}return max(a,b);
}
int dx[]={0,1,0,-1,1,-1,-1,1};
int dy[]={1,0,-1,0,1,1,-1,-1};
const int MOD = 1e9+7;
const int INF = 1e18+10;

/*----------------------------------------------*/

signed main(){
  int n,m;
  cin>>n>>m;
  int P[100000],Y[100000];
  vi V[100001];
  rep(i,m){
    cin>>P[i]>>Y[i];
    V[P[i]].pb(Y[i]);
  }
  rep(i,n+1) sort(all(V[i]));

  rep(i,m){
    // int l=0,r=V[P[i]].size(),mid;
    // while(l+1<r){
    //   mid=(l+r)/2;
    //   if(V[P[i]][mid]>Y[i]) r=mid;
    //   else l=mid;
    // }
    auto ite = lower_bound(all(V[P[i]]),Y[i]);
    int l=ite-V[P[i]].begin();
    cout<<setw(12)<<setfill('0')<<P[i]*1000000+l+1<<endl;
  }
  return 0;
}


Measured memory_bytes: 8576