akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAX(a,b,c) max(a,max(b,c))
#define MIN(a,b,c) min(a,min(b,c))

int main()
{
	string a,b;
	cin>>a>>b;
	string tmp=b;
	tmp.erase(b.size()-1,1);
	
	if(tmp==a)
		cout<<"Yes"<< endl;
	else
		cout<<"No"<< endl;
	
	return 0;
}


Measured memory_bytes: 3596
#include <cstdio>
using namespace std;

int main(int argc, char* argv[]) {
    int imax = 10;
    char s[imax + 1];
    fgets(s, imax + 1, stdin);

    int n = 0;
    for (int i = 0; i < imax; i+=2) {
        if (s[i] == '\0' ||
            s[i] == '\n' ||
            s[i] == '\r') break;
        if (i + 1 < imax) {
            if (s[i + 0] == 'h' &&
                s[i + 1] == 'i') {
                ++n;
            } else {
                n = 0;
                break;
            }
        }
    }

    if (n > 0) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }

    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

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

    int n; cin >> n;
    int count = 0;
    F0R(i, n) {
        int cur; cin >> cur;
        while (cur % 2 == 0) {
            cur /= 2;
            count++;
        }
    }
    cout << count << endl;
    return 0;
}

// read the question correctly (ll vs int)
// template by bqi343

Measured memory_bytes: 256
/*
    Code by CNH_Tourist
    Date Created: 10/6/2019
*/
#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unrolled-loops")

using namespace std;

/*---------------------Define--------------------*/
#define inp "TestCode.inp"
#define out "TestCode.out"
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define FileInOut freopen(inp,"r",stdin);freopen(out,"w",stdout);
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define mp make_pair
#define X first
#define Y second
#define pi acos(-1)
#define pii pair<int,int>
#define ppiii pair< pair <int,int> ,int>
#define INF 1000000
#define endl '\n'
#define ll long long
#define pq priority_queue
const ll mod=1e9+7;
int test=1;
const int N=100100;
/*-----------------------------------------------*/

/*---------------SegmentTree Build---------------
void build(int node, int Start, int End)
{
    if(Start == End)
    {
        // Leaf node will have a single element
        tree[node] = A[start];
    }
    else
    {
        int mid = (Start + End) / 2;
        // Recurse on the left child
        build(2*node, Start, mid);
        // Recurse on the right child
        build(2*node+1, mid+1, End);
        // Internal node will have the sum of both of its children
        tree[node] = tree[2*node] + tree[2*node+1];
    }
}
------------------------------------------------*/

int n,k;
int a[110];
int c[100100];

int main()
{
    FAST
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=k;i++)
    {
        int ok=0;
        for(int j=1;j<=n;j++)
        {
            if(i<a[j]) continue;
            ok=1-c[i-a[j]];
            if(ok)break;
        }
        c[i]=ok;
    }
    if(c[k]) cout<<"First";
    else cout<<"Second";
}


Measured memory_bytes: 640
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let a: i32 = read();
    let b: i32 = read();
 
    if a > b {
        println!("{}", "a > b");
    } else if a == b {
        println!("{}", "a == b");
    } else {
        println!("{}", "a < b");
    }
}



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

int main(){
    int n;
    cin >> n;
    vector<int> s(n);
    for(int i = 0;i < n;i++){
        cin >> s[i];
    }
    int q;
    cin >> q;
    vector<int> t(q);
    for(int i = 0;i < q;i++){
        cin >> t[i];
    }
    
    int count = 0;
    for(int i = 0;i < q;i++){
        s.push_back(t[i]);
        int j = 0;
        while(s[j] != t[i]){
            j++;
        }
        if(j != n){
            count++;
        }
      	s.pop_back();
    }
    cout << count << endl;
}


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

int main(){
    int X ;
    cin >> X;
    if(X<600) cout << "8" ;
    else if(X<800) cout <<  "7";
    else if(X<1000) cout << "6";
    else if(X<1200) cout << "5";
    else if(X<1400) cout << "4";
    else if(X<1600) cout << "3";
    else if(X<1800) cout << "2";
    else cout << "1";
}

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

// chmin
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

// res[i][c] := i 文字目以降で最初に文字 c が登場する index (存在しないときは n)
vector<vector<int> > calcNext(const string &S) {
    int n = (int)S.size();
    vector<vector<int> > res(n+1, vector<int>(26, n));
    for (int i = n-1; i >= 0; --i) {
        for (int j = 0; j < 26; ++j) res[i][j] = res[i+1][j];
        res[i][S[i]-'a'] = i;
    }
    return res;
}

int main() {
    string S; cin >> S;
    int n = (int)S.size();
    
    // 前処理配列
    auto next = calcNext(S);

    // DP
    vector<int> dp(n+1, 1<<29); // DP テーブル
    vector<pair<char, int> > recon(n+1, {'?', n}); // 復元用テーブル
    dp[n] = 1;
    for (int i = n - 1; i >= 0; --i) {
        for (int j = 0; j < 26; ++j) {
            // 次の文字がないとき
            if (next[i][j] == n) {
                if (dp[i] > 1)
                    dp[i] = 1, recon[i] = {'a'+j, n};
            }
            // 次の文字があるとき
            else if (chmin(dp[i], dp[next[i][j] + 1] + 1))
                recon[i] = {'a'+j, next[i][j] + 1};
        }
    }
    
    // 復元
    string res = "";
    int index = 0;
    while (index < n) {
        auto p = recon[index];
        res += p.first;
        index = p.second;
    }
    cout << res << endl;
}

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

int test(int i){
      int k=0;

      while(i > 0){
            k += i % 10;
            i /=10;
      }
      return k;
}

int main(){
      int N,A,B,ans=0;
      cin >> N >> A >> B;

      for(int i = 0; i <= N;i++){
            int check = test(i);
            if(check >= A && check <= B)ans+=i;
      }
      cout << ans << endl;
}

Measured memory_bytes: 256
double P[102][101];
char L[101],B[101];
main(){
	int N,T,l,b,x,t,n,k;
	for(;scanf("%d%d%d%d",&N,&T,&l,&b),N;){
		memset(P,0,sizeof(P));
		memset(L,0,sizeof(L));
		memset(B,0,sizeof(B));
		for(;l--;)scanf("%d",&x),L[x]=1;
		for(;b--;)scanf("%d",&x),B[x]=1;
		P[0][0]=1;
		for(t=0;t<T;P[t+1][N]+=P[t][N],t++)for(n=0;n<N;n++){
			for(k=1;k<=6;k++){
				x=n+k;
				if(x>N)x=2*N-x;
				if(B[x])x=0;
				double d=P[t][n]/6;
				if(L[x])P[t+2][x]+=d;
				else P[t+1][x]+=d;
			}
		}
		printf("%f\n",P[T][N]);
	}
exit(0);}

Measured memory_bytes: 720
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

n,m = map(int,readline().split())
c = set()
v = {}
for i in range(m):
  a,b = map(int,readline().split())
  d = list(map(int,readline().split()))
  e = 0
  for j in d:
    e += 2**(j-1)
  if i >= 1:
    s = list(c)
    for k in s:
      if not k|e in c:
        c.add(k|e)
        v[k|e] = a+v[k]
      else:
        v[k|e] = min(v[k|e],a+v[k])
  if not e in c:
    c.add(e)
    v[e] = a
  else:
    v[e] = min(v[e],a)
    
if 2**n-1 in c:
  print(v[2**n-1])
else:
  print(-1)

Measured memory_bytes: 44252
#include<bits/stdc++.h>
#define rep(n) for(int i=0;i<(n);i++)
#define rep1(n) for(int i=1;i<=(n);i++)
#define all(n) n.begin(),n.end()
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
using namespace std;
using ll=long long;
using pii=pair<int,int>;
#define pb push_back
#define debug(x) cout<<#x<<"="<<x<<'\n';
const ll mod = 1000000007;
ll dp[105][100005];
ll pre[100005];
ll lim[105];

int main(){
      int n,k;
      cin>>n>>k;
      dp[0][0] = 1;
      pre[0] = 1;
      for(int i=1;i<=k;i++){
        pre[i] = pre[i-1] + dp[0][i];

      }

      for(int i=1;i<=n;i++){
        cin>>lim[i];
      }

      for(int i=1;i<=n;i++){
          for(int j=0;j<=k;j++){
              if(j>lim[i]) dp[i][j] = pre[j] - pre[j-lim[i]-1];
              else dp[i][j] = pre[j];
              dp[i][j] = (dp[i][j]+mod)%mod;
          }
          pre[0] = dp[i][0];
          for(int j=1;j<=k;j++){
            pre[j] = pre[j-1] + dp[i][j];
            pre[j] %= mod;
          }

      }
      cout<<dp[n][k]<<'\n';



}


Measured memory_bytes: 79360
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<string>
#define rep(i,N) for(int i=0;i<N;i++)

long long  INF=1000000000000000000;
long long mod=1000000007;
using namespace std;


int main(){

string s;
cin>>s;
long long K;
cin>>K;
char before=s[0];
int renzoku=1;
long long ans=0;

for(int i=1;i<s.size();i++){
    if(s[i]==before){
        renzoku++;
    }
    else{
        ans+=renzoku/2;
        renzoku=1;
    }
    before=s[i];
}
if(renzoku>1){
    ans+=renzoku/2;
    }
//頭の連続をみる
char before2=s[0];
int k=0;
int hazime=0;
char last=s[s.size()-1];
int owari=0;
int l=s.size()-1;
while(s[k]==s[0] && k<s.size()){
    hazime++;
    k++;
}

while(s[l]==last && l>-1){
    owari++;
    l--;
}
if(s.size()==1){
    ans=K/2;
    cout<<ans<<endl;
    return 0;
}
if(hazime==s.size()){
    ans=(s.size()*K)/2;
    cout<<ans<<endl;
    return 0;
}
if(s[0]!=s[s.size()-1] || (hazime+owari)%2==1 ){
ans*=K;
cout<<ans<<endl;
return 0;
}
else{
ans*=K;
ans+=(K-1);
cout<<ans<<endl;
return 0;
}

 return 0;
}
/*
issii
2

4


qq
81

81

cooooooooonteeeeeeeeeest
999993333

8999939997
*/

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define INF 1e9
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; }

int main(){
    int N,A,B,C,D;
    string S;
    cin>>N>>A>>B>>C>>D>>S;
    S="#"+S+"#";
    auto can_reach=[&](int start,int end){
        for(int i=start;i+1<=end;i++){
            if(S[i]=='#' && S[i+1]=='#') return false;
        }
        return true;
    };
    
    if(!can_reach(A,C) || !can_reach(B,D)){
        cout<<"No"<<endl;
        return 0;
    }
    
    if(C>D){
        bool snuke_can_over=false;
        for(int i=B;i<=D;i++){
            if(S[i-1]=='.' && S[i]=='.' && S[i+1]=='.'){
                snuke_can_over=true;
            }
        }
        if(!snuke_can_over){
            cout<<"No"<<endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;
}

Measured memory_bytes: 772
#include <iostream>
#include <cstdlib>
#include <vector>
#include <stdio.h>
using namespace std;

int main()
{
  int N, K, Q;
  cin >> N >> K >> Q;
  vector<int> score(N);
  int t;
  for (int i = 0; i < Q; i++){
    scanf("%d\n", &t);
    score.at(t-1) += 1;
  }
  for (int i = 0; i < N; i++){
    if (score.at(i) - Q + K >= 1){
      printf("Yes\n");
    }
    else{
      printf("No\n");
    }
  }
}

Measured memory_bytes: 1024
#include<stdio.h>

int main()
{
    double x,y;
    int d,r,X,Y;
    double f;
    scanf("%lf %lf",&x, &y);
    d=x/y;
    X=x;
    Y=y;
    r=X%Y;
    f=x/y;
    printf("%d %d %lf\n",d,r,f);
    return 0;
}



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

using namespace std;
int apples[205];

int main() {

	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);

	int n, l;
	cin >> n >> l;
	int apple_pie = 0;
	for (int i = 1; i <= n; ++i) {
		apples[i] = l + i - 1;
		apple_pie += apples[i];
	}
	int diff = abs(apples[1]);
	int apple = apples[1];
	for (int i = 2; i <= n; ++i) {
		if (abs(apples[i]) < diff) {
			diff = abs(apples[i]);
			apple = apples[i];
		}
	}
	cout << apple_pie - apple << '\n';
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int lint
typedef long long lint;
typedef pair<int,int> P;
const int    INF=(int)1e9;
const int    MOD=(int)1e9+7;
const double EPS=(double)1e-10;
struct Accelerate_Cin{
    Accelerate_Cin(){
        cin.tie(0); ios::sync_with_stdio(0);cout<<fixed<<setprecision(20);
    };
};



signed main(){
  int R,G;cin>>R>>G;

  int ans=2*G-R;

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


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

int dp[502][2][10][500][3], m, len[2];
char S[2][550];

int solve(int o) {
	memset(dp, 0, sizeof(dp));
	dp[0][0][0][0][0] = 1;
	rep(i, len[o])rep(j, 2)rep(k, 10)rep(l, m)rep(d, 3) {
		if (dp[i][j][k][l][d] == 0)continue;
		int s, g, p = S[o][i] - '0';
		if (d == 1)s = k + 1, g = (j ? 9 : p);
		else if (d == 2)s = 0, g = (j ? k - 1 : min(k - 1, p));
		else s = 0, g = (j ? 9 : p);
		for (int x = s; x <= g; x++) {
			if (x&&k == x)continue;
			int y;
			if (d == 1)y = 2;
			else if (d == 2)y = 1;
			else {
				if (k == 0)y = 0;
				else if (x < k)y = 1;
				else y = 2;
			}
			(dp[i + 1][j || x < p][x][(l * 10 + x) % m][y] += dp[i][j][k][l][d]) %= MOD;
		}
	}
	int sum = 0;
	rep(j, 10)rep(t, 3) {
		(sum += dp[len[o]][1][j][0][t]) %= MOD;
		if (o)(sum += dp[len[o]][0][j][0][t]) %= MOD;
	}
	return sum;
}
int main() {
	scanf("%s%s%d", S[0], S[1], &m);
	rep(i, 2)len[i] = strlen(S[i]);
	printf("%d\n", (solve(1) + MOD - solve(0)) % MOD);
}

Measured memory_bytes: 62032
#include<stdio.h>

#define N 101
#define WHITE  3
#define GRAY   4
#define BRACK  5

void DFSvisit(int);
void DFS();

int a[N][N],n,time=0,color[N],d[N],f[N],k[N];

int main(){
  int i,j,u,v;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      a[i][j]=0;
    }
  }
  for(i=0;i<n;i++){
    scanf("%d%d",&u,&k[i]);
    for(j=0;j<k[i];j++){
      scanf("%d",&v);
      a[u-1][j]=v-1;
    }
  }

  DFS();
  for(i=0;i<n;i++){
    printf("%d %d %d\n",i+1,d[i],f[i]);
  }
  return 0;
}

void DFSvisit(int u){
  int v;
  color[u]=GRAY;
  time++;
  d[u]=time;
  for(v=0;v<k[u];v++){
    if(a[u][v] && color[a[u][v]]==WHITE)
      DFSvisit(a[u][v]);
  }
  color[u]=BRACK;
  f[u]=++time;
}

void DFS(){
  int i;
  time=0;
  for(i=0;i<n;i++){
    color[i]=WHITE;
  }
  for(i=0;i<n;i++){
    if(color[i]==WHITE) DFSvisit(i);
  }
}

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

long long int n, k, i, a;
long long int am[5] = {4, 2, 0, 9, 7};

int main(){
    scanf("%lld%lld", &n, &k);
    for(i = 0; i < 5; ++i){
        if(((k - am[i] + 11) * 7) % 11 + 1 < n - 1){
            a += ((n - 3 - ((k - am[i] + 11) * 7) % 11) / 11 + 1);
        }
    }
    cout << a << endl;
    return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<algorithm>
using lint=int64_t;
using namespace std;

int main()
{
	int N,M;
	int A[25][25];
	int B[25];
	int C;
	
	cin >> N >> M >> C;
	for(int i=0;i<M;i++)
		cin >> B[i];
	for(int i=0;i<N;i++)
		for(int j=0;j<M;j++)
			cin >> A[i][j];
	
	int ans=0;
	for(int i=0;i<N;i++)
	{
		int tmp=0;
		for(int j=0;j<M;j++)
		{
			tmp+=A[i][j]*B[j];
		}
		tmp+=C;
		if(tmp>0)
			ans++;
	}
	
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 256
#define	_USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cctype>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <string>
#include <set>
#include <complex>
#include <utility>
#include <numeric>
using namespace std;
const int INF=1<<30;

typedef pair<int,int> P;

int main(){
	
	int n;
	cin>>n;
	vector<long long int> a(n);
	vector<long long int> idx(n);
	set<int> S;
	for(int i=0;i<n;i++){
		cin>>a[i];
		idx[a[i]-1] = i;
	}
	
	long long int ans=0;
	S.insert(n);
	S.insert(-1);
	for(size_t i=0;i<n;i++){
		int now = idx[i];
		auto itr = S.upper_bound(now);
		int r = *itr-1;
		itr = S.lower_bound(now);
		itr--;
		int l= *itr+1;
		S.insert(now);
		ans+=(i+1)*(r-now+1)*(now-l+1);
	}
	cout<<ans<<endl;
	
}

Measured memory_bytes: 12800
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<string>
#include<utility>
#include<array>
#include<set>
#define EPS (1e-7)
using namespace std;






int main() {


	int H, W;
	cin >> H >> W;

	vector<vector<char>> campus(H);
	vector<char> inner(W,'.');
	string ans = "Yes";

	for (auto i = 0; i < H; i++)
	{
		for (auto j = 0; j < W; j++)
		{
			cin >> inner[j];
		}
		campus[i] = inner;
	}


	for (auto i = 0; i < H; i++)
	{
		for (auto j = 0; j < W; j++)
		{
			
			if (campus[i][j] == '.')continue;
			else {
				vector<char> around;
				if (i != 0) 	around.push_back(campus[i - 1][j]);
				if (i != H - 1)around.push_back(campus[i + 1][j]);
				if (j != 0)around.push_back(campus[i][j - 1]);
				if (j != W - 1)around.push_back(campus[i][j + 1]);
				int count = 0;
				for (auto k = 0; k < around.size(); k++)
				{
					if (around[k] == '#')count += 1;
				}
				if (count == 0) {
					ans = "No";
					break;
				}
			}

		}
		if (ans == "No")break;
	}

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

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
 
int main() {
   string n;
   
 
   cin >> n;
  
   if(n[0]==n[1]&&n[1]==n[2]){
     
     cout << "Yes" << endl;
     
   }else if(n[1]==n[2]&&n[2]==n[3]){
     cout << "Yes" << endl;
   }else{
     cout << "No" << endl;
   }
  
   
  
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    int ans = 0;
    for(int i = 1; i < n; ++i)
        ans += i;
    for(int i = 1; i < m; ++i)
        ans += i;
    printf("%d", ans);
    return 0;
}


Measured memory_bytes: 256
n,d = gets.chomp.split.map(&:to_i)
distance = n.times.map{gets.split.map(&:to_i)}

kotae = 0
(0..n-1).each do |i|
  if ((distance[i][0]**2 + distance[i][1]**2)**(1/2.0)) <= d
    kotae += 1
  end
end

puts kotae

Measured memory_bytes: 28832
#include <iostream>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;

#define abs(N) ((N>0)?N:-1*N)
#define min(A,B) ((A>B)?B:A)
#define max(A,B) ((A<B)?B:A)
#define print(S) (cout << S)
#define println(S) (cout << S << endl)

int main(){
	double x1,y1,x2,y2;
	double d;
	cin >> x1 >> y1 >> x2 >> y2;

	d = sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1));

	printf("%.5f\n",d);

	return 0;
}



Measured memory_bytes: 3176
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <math.h>
#include <time.h>
using namespace std;
int main() {
	long long int a, b[100000], cnt = 1, ans = 0;
	cin >> a;
	for (int i = 0; i < a; i++) {
		cin >> b[i];
	}
	sort(b, b + a);
	for (int i = 0; i < a; i++) {
		if (b[i] == b[i + 1]) {
			cnt++;
		}
		else {
			if (cnt % 2 == 0) {
				cnt = 1;
			}
			else {
				ans++;
				cnt = 1;
			}
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 1152
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(int i=0;i<N;++i)
typedef long long int LL;

LL N, ans;
std::vector<std::pair<LL, LL> > d;

int main()
{
	in>>N;
	d.resize(N);
	rep(i,N)
	{	in>>d[i].first>>d[i].second;}

	std::sort(d.begin(),d.end());
	ans=d[N-1].first+std::max<int>(0,d[N-1].second);

	out<<ans<<std::endl;
	return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
 
struct node {
    string p;
};
 
int l,n;
vector <node> s ;
 
bool cmp (const node &a, const node &b) {
	return a.p<b.p ;

}
 
int main () {
//	freopen("subtask1_06.in","r",stdin) ;
    cin>>n>>l ;

    for (int i=1;i<=n;++i) {
		node tt ;
		cin >> tt.p ;
		s.push_back(tt) ;
	}
    sort (s.begin(),s.end(),cmp);
    for (int i=0;i<s.size();++i) cout<<s[i].p;
    cout<<endl;
    return 0;
}


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

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

using namespace std;

template <class T, class U> void amin(T& x, U y) {if (x > y) x = y;}

int main(void)
{
    const int N_MAX = 50000;
    const int M_MAX = 20;
    int n, m;
    int d[M_MAX];
    cin >> n >> m;
    REP(i, m) cin >> d[i];
    int dp[N_MAX + 1];
    dp[0] = 0;
    REP(i, n + 1) {
        dp[i] = i;
        REP(j, m) {
            if (i - d[j] >= 0) {
                amin(dp[i], dp[i - d[j]] + 1);
            }
        }
    };
    cout << dp[n] << endl;
    return 0;
}



Measured memory_bytes: 3288
# -*- coding: utf-8 -*-
from sys import stdin
from operator import itemgetter
# stdin = open("sample.txt")

s = stdin.readline().rstrip()
t = s[0:(len(s)-1)//2]
u = s[(len(s)+3)//2 - 1:len(s)]

if t == u and t == t[::-1]:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3060
def main():
    N = int(input())
    ends_A = 0
    starts_B = 0
    B_A = 0
    include_AB = 0
    for i in range(N):
        s = input()
        
        
        if s[-1] == "A" and s[0] == "B":
            B_A += 1
        elif s[-1] == "A":
            ends_A += 1
        elif s[0] == "B":
            starts_B += 1

        aflag = 0
        for c in s:
            if aflag and c == "B":
                include_AB += 1
            if c == "A":
                aflag = True
            else:
                aflag = False
    if B_A != 0 and ends_A == 0 and starts_B == 0:
        print(B_A - 1 + include_AB)
    else:
        print(min(ends_A+B_A, starts_B+B_A) + include_AB)
    # cur_B_A = 0
    # cur_endA = 1
    # cur_startB = 2
    # cur_none = 3
    # current = -1
    # if ends_A != 0:
    #     current = cur_endA
    #     ends_A -= 1
    # elif starts_B != 0:
    #     current = cur_startB
    #     starts_B -= 1
    # elif B_A != 0:
    #     current = cur_B_A
    #     B_A -= 1
    # else:
    #     print("0")
    #     return
    # while True:
    #     if current == cur_startB:
    #         if end_a != 0:
    #             end_a -= 1

            
            
if __name__ == "__main__":
    main()

Measured memory_bytes: 3188
//
//  main.cpp
//  AC
//
//  Created by makinofuya on 2019/07/08.
//  Copyright © 2019 makinofuya. All rights reserved.
//
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>
#include <math.h>
#include <map>

typedef long long ll;
using namespace std;
#define mod 1000000007
#define rep(i,n) for(ll i=0;i<n;i++)
#define out(s) cout << s << endl


int main(){
    int n,k;cin >> n >> k;
    vector<int> l(n);
    rep(i,n)cin >> l[i];
    int ans=0;
    sort(l.begin(),l.end());
    reverse(l.begin(),l.end());
    for(int i=0;i<k;i++){
        ans+=l[i];
    }
    cout << ans << endl;
    return 0;
}


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

int main(){
    double r;
    cin >> r;
    double pi = acos(-1);
    printf("%.5f %.5f\n", r * r * pi, 2 * r * pi);

}


Measured memory_bytes: 3284
#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>
#include <string>
#include <cmath>
#include <map>
#include <set>

using namespace std;

int main()
{
    long long N, a;

    cin >> N;

    bool flag = false;
    for (int i = 0; i < N; i++)
    {
        cin >> a;
        if(a % 2 == 1)
        {
            flag = true;
        }
    }

    cout << (flag == true ? "first" : "second") << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<string>
#include<iostream>
#include<cmath>
#include<set>
#include<stack>
#include<queue>
#include<unistd.h>
#include<stdio.h>
#include<cstring>
using namespace std;

int main()
{
	int a,b,c;
	cin>>a>>b>>c;
	if(b>=a*c) cout<<c<<endl;
	else
	{
		cout<<b/a<<endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
/*{{{*/  //template
#define rep(i,n) for(int i=0;i<(int)(n);i++)
constexpr int INF = numeric_limits<int>::max()/2;
constexpr long long LINF = numeric_limits<long long>::max()/3;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define sz(x) (int)(x).size()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
//struct fin{ fin(){ cin.tie(0); ios::sync_with_stdio(false); } } fin_;
struct Double{ double d; explicit Double(double x) : d(x){} };
ostream& operator<<(ostream& os,const Double x){ os << fixed << setprecision(20) << x.d; return os; }
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
template<typename T> ostream& operator<<(ostream& os,const set<T>& st){ os<<"{"; for(T v:st) os<<v<<","; os <<"}"; return os; }
template<typename T,typename U> inline void chmax(T &x,U y){ if(y>x) x = y; }
template<typename T,typename U> inline void chmin(T &x,U y){ if(y<x) x = y; }
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }
//constexpr double eps = 1e-14; 
constexpr double eps = 1e-10; 
constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};
/*}}}*/

ll N,K;

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

    if(K==0){
        cout << N * N << endl;
        return 0;
    }

    ll ans = 0;
    for(ll b=K+1;b<=N;b++){
        ll m = (N+1)/b;
        ll cnt = m * (b - K);
        ans += cnt;
        if(m*b+K <= N){
            ans += N-(m*b+K)+1;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <algorithm>
#include <climits>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <iostream>
#include <math.h>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define str string
#define deb_arr(arr,n) for(ll i=0;i<(n);i++){ cout << (arr)[i] << " ";}
#define in_arr0(arr,n) for(ll i=0;i<(n);i++){ cin >> (arr)[i]; }
#define in_arr1(arr,n) for(ll i=1;i<=(n);i++){ cin >> (arr)[i];}
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> pbds;
#define vll vector<ll> 
#define fr(n) for(i=0;i<(n);i++)
#define fr1(n) for(i=1;i<=(n);i++)
#define pll pair<ll,ll>
#define f first
#define s second
#define vpll vector<pll>
#define ump unordered_map
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define IN(a,b) ((a).find(b)!=(a).end())
#define pb push_back
#define mkp make_pair
#define PI M_PI
#define INF 1e18
#define deb(x) if(ON) cout << #x <<" : " << x << endl
#define fast ios_base::sync_with_stdio(false)
#define io cin.tie(NULL),cout.tie(NULL)
#define ON !false
ll dx[]={0,-1,0,1};
ll dy[]={1,0,-1,0};
const ll mod=1e9+7;
inline ll add(ll a,ll b){
    return  ((a%mod)+(b%mod)+mod)%mod;
}
inline ll mul(ll a,ll b){
    return ((a%mod)*(b%mod)+mod)%mod;
}
void pause(ll id){
    cout << "Waiting " << id << endl;
    cin >> id;
}

const int mxn=1e5+10;


void init(){

    return ;
}


signed main(){
    fast;
    io;
    if(!true){
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    }
    init();
    ll i,j;
    ll a,b,c,d;
    cin >> a >> b >> c >> d;
    bool flag=true;
    while(true){
        if(flag){
            c=max(0ll,c-b);  
            if(c==0){
                cout << "Yes" << endl;
                return 0;
            } 
            flag=false;
        }
        else{
            a=max(0ll,a-d);
            if(a==0){
                cout << "No" << endl;
                return 0;
            }
            flag=true;
        }
    }
   
    return 0;
}


Measured memory_bytes: 3656
#include<iostream>
#include<vector>
#include<cstdlib>
using namespace std;

void chmin(long long int &a,long long int b){
  if(a>b){
    a=b;
  }
}

int main(){
  int N,K;
  cin>>N>>K;
  
  int h[N+K];
  for(int i=0;i<N;i++)cin>>h[i];
  
  long long int dp[N+K];
  for(int i=0;i<N;i++)dp[i]=1000000010;
  
  dp[0]=0;
  
  for(int i=0;i<N;i++){
    for(int j=1;j<=K;j++){
      
    	chmin(dp[i+j],dp[i]+abs(h[i]-h[i+j]));
    	//chmin(dp[i+2],dp[i]+abs(h[i]-h[i+2]));
    }
  }
  cout <<dp[N-1]<<endl;
    
  
}


Measured memory_bytes: 1408
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rngll(chrono::steady_clock::now().time_since_epoch().count());
template<typename T> T ctmax(T &x, const T &y){ return x = max(x, y); }
template<typename T> T ctmin(T &x, const T &y){ return x = min(x, y); }
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;



int main(){
	cin.tie(0)->sync_with_stdio(0);
	int n;
	cin >> n;
	vector<tuple<int, int, int>> a(n);
	for(int i = 0; i < n; ++ i){
		int t, x, y;
		cin >> t >> x >> y;
		a[i] = tuple<int, int, int>{t, x, y};
	}
	a.insert(a.begin(), tuple<int, int, int>{0, 0, 0});
	for(int i = 1; i <= n; ++ i){
		int pt, px, py, t, x, y;
		tie(pt, px, py) = a[i - 1];
		tie(t, x, y) = a[i];
		if(t - pt < abs(x - px) + abs(y - py) || (t - pt) % 2 ^ (abs(x - px) + abs(y - py)) % 2){
			cout << "No";
			return 0;
		}
	}
	cout << "Yes";
	return 0;
}

/*

*/

////////////////////////////////////////////////////////////////////////////////////////
//                                                                                    //
//                                   Coded by Aeren                                   //
//                                                                                    //
////////////////////////////////////////////////////////////////////////////////////////

Measured memory_bytes: 2560
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <queue>

using namespace std;

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

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

  int N, K;
  cin >> N >> K;
  VI ws(N);
  REP(i,N) cin >> ws[i];

  LL lo = 0, up = 1e9, ans;
  while(lo+1 < up){
	LL mid = (lo + up) / 2;
	LL cnt = 0, acc = mid;
	REP(i,N){
	  if(ws[i] > mid){
		cnt = K+1; break;
	  }
	  if(acc + ws[i] > mid){
		++cnt;
		acc = ws[i];
	  }
	  else
		acc += ws[i];
	}
	if(cnt <= K)
	  up = mid, ans = mid;
	else
	  lo = mid;
  }

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

Measured memory_bytes: 1524
#include <cstdio>

int main() {
    int n, count = 0, count_odd = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int a;
        scanf(" %d", &a);
        if (a % 2) {
            count_odd = (count_odd + 1) % 2;
        } else {
            count = 1;
        }
    }
    if ((count == 1 && count_odd == 0) || (count == 0 && count_odd == 0)) {
        printf("YES\n");
    } else {
        printf("NO\n");
    }
    return 0;
}


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

int main()
{
	int d;
	while (cin >> d) {
		int sum = 0;
		for (int i = d; i <= 600 - d; i += d) {
			sum += (d*i*i);
		}
		cout << sum << endl;
	}
    return 0;
}

Measured memory_bytes: 1160
import sys
from fractions import gcd
from functools import reduce

n, k = map(int, input().split())
arr = list(map(int, input().split()))

if k in arr:
    print("POSSIBLE")
    sys.exit()

if k > max(arr):
    print("IMPOSSIBLE")
    sys.exit()

div = reduce(gcd, arr)

print("POSSIBLE" if k % div == 0 else "IMPOSSIBLE")

Measured memory_bytes: 16284
# -*- coding: utf-8 -*-
"""
Created on Fri Jun 19 16:42:06 2020

@author: NEC-PCuser
"""

import heapq

N, M = map(int, input().split())

A = list(map(int, input().split()))

B_C = []
for i in range(M):
    b_c = list(map(int, input().split()))
    B_C.append(b_c)
 
B_C = sorted(B_C, reverse=True, key=lambda x: x[1])
ans = sum(A)
heapq.heapify(A)
i = 0 

while True:
    for j in range(B_C[i][0]):
        c = heapq.heappop(A)
        ans -= c
        if c < B_C[i][1]:
            heapq.heappush(A, B_C[i][1])
            ans += B_C[i][1]
        else:
            heapq.heappush(A, c)
            ans += c
            break
    else:
        i += 1
        if (len(B_C) == i):
            break
        continue
    break

print(ans)


Measured memory_bytes: 33732
def comb(a,b):
    x = 1
    for i in range(a-b+1,a+1):x*=i
    for i in range(1,b+1):x//=i
    return(x)

n = int(input())

dict_num = {}

for _ in range(n):
    s = ''.join(sorted(list(input())))
    if(s in dict_num):dict_num[s]+=1
    else:dict_num[s] = 1

c=0
for k,v in dict_num.items():
    if(v>=2):c += comb(v,2)
print(c)

Measured memory_bytes: 17808
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
typedef pair<int,int> P;
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
const ll mod=1000000007;
//ios_base::sync_with_stdio(false);
//cin.tie(NULL);
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
int main(){
int n;
cin>>n;
vector<ll> a(n),sum(n+1,0);
for(int i=0;i<n;i++){
    cin>>a[i];
}
vector<vector<ll>> dat(60,vector<ll>(n,0)),zer(60,vector<ll>(n,0));
for(int i=0;i<60;i++){
  for(int j=0;j<n-1;j++){
           if(a[j]&(1ll<<i)){
             dat[i][j+1]+=dat[i][j]+1;
             zer[i][j+1]+=zer[i][j];
           }
           else {
             dat[i][j+1]+=dat[i][j];
             zer[i][j+1]+=zer[i][j]+1;
           }
  }
}
ll ans=0;
for(int i=0;i<60;i++){
  ll now=(1LL<<i);
  now%=mod;
  for(int j=1;j<n;j++){
           if(a[j]&(1ll<<i))(ans+=now*zer[i][j]%mod)%=mod;
           else (ans+= now*dat[i][j]%mod)%=mod;
  }
}
cout<<ans<<endl;
}



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

 int main(){
  int n,c;
  cin>>n;
  c=n%10;
   if(c==3){
    cout<<"bon";
   }
   else if(c==0||c==1||c==6||c==8){
    cout<<"pon";
   }
   else{
    cout<<"hon";
   }




  return 0;
 }


Measured memory_bytes: 3672
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

A = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
K = int(read())
print(A[K-1])

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

struct edge {
    int to, time;
};

void dfs(vector<vector<edge>> const& g, int v, int d, int& sum, int& ma, vector<bool>& visited) {
    visited[v] = true;
    for(auto& e : g[v]) {
        if(visited[e.to]) {
            continue;
        }
        if(g[e.to].size() == 1) {
            ma = max(ma, d);
        } else {
            sum += e.time * 2;
            dfs(g, e.to, d + e.time, sum, ma, visited);
        }
    }
}

int main() {
    int N;
    while(cin >> N, N) {
        vector<vector<edge>> g(N);
        for(int i=0; i<N-1; ++i) {
            int a, b, t;
            cin >> a >> b >> t;
            a--; b--;
            g[a].push_back((edge){b, t});
            g[b].push_back((edge){a, t});
        }
        int sum = 0, ma = 0;
        vector<bool> visited(N);
        dfs(g, 0, 0, sum, ma, visited);
        cout << sum - ma << endl;
    }
}


Measured memory_bytes: 3108
A, B = map(int, input().split())

for i in range(A+1):
    for j in range(A+1-i):
        k = A-i-j
        if 10000*i + 5000*j + 1000*k == B:
            print(i, j, k, flush=True)
            exit()

print(-1, -1, -1)


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

using namespace std;

int main() {

	int a, b, c,d, p;
	cin >> a >> b >> c >> d >>p;
	
	int cost = 0;
	if (p <= c) { cost = b; }
	else {
		cost = b + (p - c)*d;
	}
	cost = min(a*p, cost);
	cout << cost << endl;
}


Measured memory_bytes: 3080
/*huypheu
5
1 2 3 4 5
*/

#include <bits/stdc++.h>
#define int long long
using namespace std;

int a[1000007],dem[1000007];
int val[1000007];

signed main()
{
	int n;
	cin >> n;
	int su=0;
	for(int i=0;i<n;i++)
	{
		cin >> a[i];
		su+=a[i];
		if(a[i]<0) 
		{
			cout << "NO\n";
			return 0;
		}
	}
	int tong=(n*(n+1))/2;
	if(su%tong!=0) 
	{
		cout << "NO\n"; return 0;
	}
	else
	{
		int k=su/tong;
		int cal=0;
		for(int i=0;i<n;i++)
		{
			int ka=k-a[(i+1)%n]+a[i];
			if(ka%n==0)
			{
				dem[i]=ka/n;
				cal+=dem[i];
				if(dem[i]<0) 
				{
					cout << "NO\n";
					return 0;
				}
			}
			else
			{
				cout << "NO\n";
				return 0;
			}
		}
		// for(int i=0;i<n;i++)
		// {
		// 	val[0]+=(n-i)*dem[i];
		// }
		// for(int i=1;i<n;i++)
		// {
		// 	val[i]=val[i-1]+cal-dem[i-1]*n;
		// }
		// for(int i=0;i<n;i++) if(val[i]==a[i]) continue; else 
		// {
		// 	cout << "NO\n";
		// 	return 0;
		// }
		// cout << "YES\n";
		if(cal==k) cout << "YES\n"; else cout << "NO\n";

		return 0;
	}
}

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

using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define debug(x)  do{cerr<<#x<<": "<<x<<"\n";}while(0)
#define debugv(x) do{cerr<<#x<<": ";for(auto&e: (x))cerr<<e<<" ";cerr<<"\n";}while(0)
#define fori(i, n) for (int i = 0; i < (int)(n); ++i)
#define forn(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n); i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
template<typename T> bool mmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }
template<typename T> bool mmin(T &m, const T q) { if (m > q) {m = q; return true;} else return false; }
#define RETURN(x) do{cout << x << '\n'; return 0;}while(0)

const int MOD = 1e9+7;
const int MAXN = 1e5+5;

int fact[MAXN], inv[MAXN], ifact[MAXN];

template<typename T, typename T1>
T mod(T x, T1 p) {
	x %= p;
	if (x < 0)
		x += p;
	return x;
}

template<typename T>
T inverse(T x, T p) {
	x = mod(x, p);
	if (x == 1)
		return x;
	return mod((1LL * (-p / x) * (inv[p % x] % p)) , p); 
	// Since inverse of p % x is already calculated.
}

int NcR(int n, int r) {
	int ret = (1LL * ifact[n - r] * ifact[r]) % MOD ;
	ret = (1LL * ret * fact[n]) % MOD;
	return ret;
}

int add(int a, int b) {
    int c = a+b;
    while(c >= MOD) c -= MOD;
    return c;
}

int mul(int a, int b) {
    int c = (1LL*a*b) % MOD;
    while(c >= MOD) c -= MOD;
    while(c < 0) c += MOD;
    return c;
}

int sub(int a, int b) {
    int c = a-b;
    while(c < 0) c += MOD;
    return c;
}


int main(int argc, char **argv) {
#ifdef OJ
    freopen("input.txt", "rt", stdin);
    //freopen("output.txt", "wt", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);

	fact[0] = 1;
	for(int i = 1; i < MAXN; i++) {
		fact[i] = 1LL * fact[i - 1] * i % MOD;
	}

	ifact[0] = 1;
	for(int i = 1; i < MAXN; i++) {
		inv[i] = inverse(i, MOD);
		ifact[i] = 1LL * ifact[i - 1] * inv[i] % MOD;
	}

    int n,k;
    cin >> n >> k;
    vector<int> a(n);
    fori(i,n) cin >> a[i];
    sort(a.begin(),a.end());

    int ans = 0;
    fore(i,k-1,n-1) {
        ans = add(ans, mul(NcR(i,k-1),a[i]));
    }

    fori(i,n-k+1) {
        int r = n-i-1;
        ans = sub(ans, mul(NcR(r,k-1),a[i]));
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1792
/*jai_ganeshdeva*/

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pu push  //  adds the value to the last of the queue 
#define lld long long int
#define ins insert /// used in set to insert the values 
#define adv advance  /// used to increment the iterator
#define mp make_pair
#define fi first
#define se second
#define all(c) c.begin(),c.end()
#define PI 3.1415926
#define INF (lld)1e18
#define vl  vector<long long int >
#define vpll vector< pair<lld ,lld> >
#define vvl vector<vector<lld> > 
#define pll pair <lld,lld>
#define modA(cccc,bbbb ,p) (((cccc+bbbb)%p+p)%p)
#define modS(cccc,bbbb ,p) (((cccc-bbbb)%p+p)%p)
#define modM(cccc,bbbb ,p) ((((cccc%p)*(bbbb%p))%p+p)%p)

long long int modp(lld a,lld p,lld n)
{
    lld d[100];
    lld i,j,k,l;
    if(n==0) return 1;
    for(i=0;n>=1;i++)
    {
        d[i]=n%2;
        n/=2;
    }
    l=i;
    long long int e=1;
    if(d[0]==1) e*=(a%p);
    for(i=1;i<l;i++)
    {
        a*=a;
        a=a%p;
        if(d[i]==1) 
        {
            e*=a;
            e=e%p;
        }
    }
    return e%p;
}
lld modInverse(lld n, lld p) 
{ 
    return modp(n, p, p-2); 
}

// lld fac[500005]; 

// void getfac(lld p)
// {
//     fac[0] = 1; 
//     for (lld i=1 ; i<=500005; i++) 
//         fac[i] = fac[i-1]*i%p; 
// }    

// long long int nCrmodp(lld n, lld r,lld p) 
// { 
//    // Base case 
//    if (r==0) 
//       return 1; 
     
//     return (fac[n]* modInverse(fac[r], p) % p * 
//             modInverse(fac[n-r], p) % p) % p; 
// }

// bool sorter(lld a, lld b)
// {
//     vector<lld> v2;
//     vector<lld> w;
//     // cout<<"A == " <<a<<"  B== "<<b;
//     while(a>=1)
//     {
//         v2.pb(a%10);
//         a/=10;
//     }
//     while(b>=1)
//     {
//         w.pb(b%10);
//         b/=10;
//     }   
       
//     reverse(all(v2));
//     reverse(all(w));
//     lld l1 = v2.size();
//     lld l2 = w.size();
//     lld  l = (l1*l2)/__gcd(l1,l2);
//     // cout<<l1<< " "<<l2<< " "<<l<< " ";
//     for(int i=0;i<l;i++)
//     {
//         if(v2[i%l1]!=w[i%l2])
//         {
//             // cout<< "   "<< (v2[i%l1] > w[i%l2])<<"\n";
//             return v2[i%l1] > w[i%l2];
//         }
//     }
//     // printf("false\n");
//     return false;
// }


lld p1=1e8 + 7,p2=998244353;
lld l,r,mid,ans;
lld n,i,j,k,g,m;
lld x,y,n1,n2,h,z,c;
lld aa=1;
lld ss=1;


void solve()
{
    x=0;
    cin>>n;
    vector<lld> v;
    for(i=0;i<n;i++)
    {
        cin>>l;
        v.pb(l);
    }
    lld a = 1000;
    for(i=1;i<n;i++)
    {
        if(v[i]>v[i-1])
        {
            x+=(a/v[i-1]);
            a%=v[i-1];
        }
        else
        {
            a+=x*v[i-1];
            x=0;
        }
    }
    a+=x*v[n-1];
    cout<<a;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lld t=1;
    
    // cin>>t;
    // cout<<t;
     // getfac(p1);
    //check the value by which modulo is to be taken
    // lld ans=0;
    // precompute();
    for(int i=0;i<t;i++)
    {
        // cout<<"Case #"<<i+1<<": ";
        solve();
        cout<<"\n";
    }
    return 0;
}

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

int main() {
    int n;
    cin >> n;
    vector<int> p(n);
    for(auto& e : p) cin >> e;
    string res = "NO";
    int count = 0;
    for(int i = 0; i < n; i++){
        if(p[i] != i+1){
            count++;
        }
    }
    if(count == 0 || count == 2){
        res = "YES";
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		@SuppressWarnings("resource")
		Scanner stdin = new Scanner(System.in);

		int inH = stdin.nextInt();
		int inW = stdin.nextInt();

		char[][] grid = new char[inH][];
		int white = 0;
		for (int h = 0; h < inH; h++) {
			grid[h] = stdin.next().toCharArray();
			for (int w = 0; w < inW; w++) {
				if (grid[h][w] == '.') {
					white++;
				}
			}
		}

		int[][] act = new int[inH][inW];
		int updateCount = 0;
		while ((act[0][0] == 0) && (updateCount < (inH * inW))) {
			act = getNextAct(act, grid, inH, inW);
			updateCount++;
		}

		if (updateCount == (inH * inW)) {
			System.out.println(-1);
			return;
		}

		int moveCount = 1;
		int h = 0;
		int w = 0;

		while ((h != (inH - 1)) || (w != (inW - 1))) {
			int nextH = h;
			int nextW = w;
			int max = act[h][w];

			if (((h - 1) >= 0) && (act[h - 1][w] > max)) {
				max = act[h - 1][w];
				nextH = h - 1;
				nextW = w;
			}
			if (((h + 1) < act.length) && (act[h + 1][w] > max)) {
				max = act[h + 1][w];
				nextH = h + 1;
				nextW = w;
			}
			if (((w - 1) >= 0) && (act[h][w - 1] > max)) {
				max = act[h][w - 1];
				nextH = h;
				nextW = w - 1;
			}
			if (((w + 1) < act[h].length) && (act[h][w + 1] > max)) {
				max = act[h][w + 1];
				nextH = h;
				nextW = w + 1;
			}

			h = nextH;
			w = nextW;
			moveCount++;
		}

		System.out.println(white - moveCount);
	}

	private static int[][] getNextAct(int[][] act, char[][] grid, int sizeH, int sizeW) {
		int[][] next = new int[sizeH][sizeW];
		for (int h = 0; h < sizeH; h++) {
			for (int w = 0; w < sizeW; w++) {
				next[h][w] = getUpdateAct(act, grid, sizeH, sizeW, h, w);
			}
		}

		return next;
	}

	private static int getUpdateAct(int[][] act, char[][] grid, int sizeH, int sizeW, int h, int w) {
		if ((h == (sizeH - 1)) && (w == (sizeW - 1))) {
			return act[h][w] + 1;
		}
		else if (grid[h][w] == '#') {
			return -1;
		}

		int max = act[h][w];
		if ((h - 1) >= 0) {
			max = Math.max(max, act[h - 1][w]);
		}
		if ((h + 1) < sizeH) {
			max = Math.max(max, act[h + 1][w]);
		}
		if ((w - 1) >= 0) {
			max = Math.max(max, act[h][w - 1]);
		}
		if ((w + 1) < sizeW) {
			max = Math.max(max, act[h][w + 1]);
		}

		return max;
	}
}


Measured memory_bytes: 24148
#include <cstdlib>
#include <iostream>
#include <string>
std::string B="4141212141412121";
int main(){
	int i,j,C[8]={},x[8]={},s,m,p,tmp;
	for(i=8;i--;)C[i]=atoi(B.substr(i,8).c_str());
	while(std::cin>>x[0]){
		m=x[0];
		for(i=1;i<8;i++){
			std::cin>>x[i];
			m+=x[i];
		}
		for(i=0;i<8;i++){
			s=0;
			for(j=0;j<8;j++){
				tmp=x[j]-B[i+j]+'0';
				s+=(tmp>0?tmp:0);
			}
			if(s<m){
				m=s;
				p=i;
			}
			else if(m==s&&C[i]<C[p])p=i;
		}
		for(i=0;i<8;i++)std::cout<<B[p+i]<<" \n"[i==7];
	}
}

Measured memory_bytes: 1188