akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <limits.h>
#include <queue>
#include <algorithm>
#include <map>

#define dprintf(s,...) printf("%s:%d" s,__func__,__LINE__,__VA_ARGS__)
using namespace std;

typedef pair<int,int> P;


const int N=10;
int mp[N][N];
int n;

int solve(){

  int i=0,j=0;
  int d=1;
  bool left=false;
  
  while(d<=n*n){

    mp[i][j]=d;
   
    if(left){
      if(n<=i+1){
	left=false;
	j++;
      }
      else if(j-1<0){
	left=false;
	i++;
      }
      else{
	j--; i++;
      }
    }
    else{
      if(n<=j+1){
	left=true;
	i++;
      }
      else if(i-1<0){
	left=true;
	j++;
      }
      else{
	j++; i--;
      }
    }
    d++;
  }

}



int main(){

  int case_n=1;
  
  while(1){
    cin>>n;
    if(n==0) break;
    solve();
    cout<<"Case "<<case_n<<":"<<endl;
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
	if(mp[i][j]>=10) cout<<" "<<mp[i][j];
        else cout<<"  "<<mp[i][j];
}
      cout<<endl;
    }
    case_n++;
  }
	       


  return 0;
}

Measured memory_bytes: 3004
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 998244353;
const ll INF = 1e16;
const ll MAX_N = 100010;
 
int main() {
    ll n;
    cin >> n;

    vl a(n);
    rep(i, n) {
        cin >> a[i];
    }

    ll k = 1 + n%2;  // 余分な✖の個数

    vvl dp(n+1, vl(k+2, -INF));  // dp[i+1][j] : a[i]まででj個余分な✖を入れたときの総和の最大値
    dp[0][0] = 0;
    rep(i, n) {
        exrep(j, 0, k) {
            chmax(dp[i+1][j+1], dp[i][j]);
            if((i+j)%2 == 0) {
                chmax(dp[i+1][j], dp[i][j] + a[i]);
            }   
            else {
                chmax(dp[i+1][j], dp[i][j]);
            }  
        }
    }
    
    out(dp[n][k]);
    re0;
}

Measured memory_bytes: 18824
A, B, C, X, Y = map(int, input().split())
cost = []
 
cost += [A*X + B*Y]
if X >= Y:
    cost += [C*2*Y + A*(X-Y)]
    cost += [C*2*X]
else:
    cost += [C*2*X + B*(Y-X)]
    cost += [C*2*Y]

print(min(cost))


Measured memory_bytes: 3060
/*input
3040
*/

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

int main() {
    int N;
    cin >> N;
    int M = (N+1000-1)/1000*1000-N;
    cout << M << endl;
}

Measured memory_bytes: 3548
#include<iostream>
#include<iomanip>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<string>
#include<utility>
#include<numeric>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;

using ll = long long;

class Stream{
public:
    Stream(){

    }
    //配列以外の入力を受け取る
    void read(){

    }
    template<typename First, typename... Rest>
    void read(First& first, Rest&... rest){
        cin >> first;
        read(rest...);
    }
    //配列を区切って出力する
    template<typename T>
    void write_vec(vector<T>& v, char divider){
        for(size_t i = 0; i < v.size(); i++){
            cout << v[i] << divider;
        }
    }
};

int main(){
    Stream io;
    
    int A, B;
    io.read(A, B);
    if(A + B >= 10){
        cout << "error";
    }
    else{
        cout << A + B;
    }
    return 0;
}

Measured memory_bytes: 256
package main
import(
	 "fmt"
)

func main() {
	var a, b, c, d, e, k int

	fmt.Scan(&a)
	fmt.Scan(&b)
	fmt.Scan(&c)
	fmt.Scan(&d)
	fmt.Scan(&e)
	fmt.Scan(&k)

	if e - a <= k {
		fmt.Println("Yay!")
	} else {
		fmt.Println(":(")
	}
}


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

const int MOD = 1000000007;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define copy(from, to) copy(from.begin(), from.end(), back_inserter(to))
#define _sort(a) sort(a.begin(), a.end())
#define _sortd(a) sort(a.rbegin(), a.rend())
#define reverse(s) reverse(s.begin(), s.end())
#define p(s) cout << (s) << endl

typedef long long ll;
using namespace std;

template<class T>
void load(vector<T> &v, int n) {
  for (int i = 0; i < n; ++i) {
    T t;
    cin >> t;
    v.push_back(t);
  }
}

template<class T>
T max(vector<T> &v) {
  return *max_element(v.begin(), v.end());
}

template<class T>
T min(vector<T> &v) {
  return *min_element(v.begin(), v.end());
}

void py(bool isUpper = false) {
  if (isUpper) {
    p("YES");
  } else {
    p("Yes");
  }
}

void pn(bool isUpper = false) {
  if (isUpper) {
    p("NO");
  } else {
    p("No");
  }
}

int main() {
  int x, y, z;
  cin >> x >> y >> z;
  cout << z << ' ' << x << ' ' <<  y << endl;
}

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

struct Edge {
    int to, id;
    Edge(int _to, int _id) : to(_to), id(_id) {}
};

int main() {
    int N, M;
    cin >> N >> M;
    vector<vector<Edge>> G(N);
    for(int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        G[a].emplace_back(b, i);
        G[b].emplace_back(a, i);
    }
    auto dfs = [&](auto &&dfs, int cur, int ng, int64_t &visited) -> void {
        visited |= 1LL << cur;
        for(auto &e : G[cur]) {
            if(visited & (1LL << e.to) || e.id == ng) continue;
            dfs(dfs, e.to, ng, visited);
        }
    };
    int ans = M;
    for(int i = 0; i < N; ++i) {
        for(auto &e : G[i]) {
            if(i < e.to) {
                int64_t visited = 0LL;
                dfs(dfs, i, e.id, visited);
                if(visited == (1LL << N) - 1) ans--;
            }
        }
    }
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
import collections
N = int(input())
a = [int(x) for x in input().split()]
rate = [0] * 8
flag = 0
for i in a:
    if 1 <= i <= 399:
        rate[0] = 1
    elif 400 <= i <= 799:
        rate[1] = 1
    elif 800 <= i <= 1199:
        rate[2] = 1
    elif 1200 <= i <= 1599:
        rate[3] = 1
    elif 1600 <= i <= 1999:
        rate[4] = 1
    elif 2000 <= i <= 2399:
        rate[5] = 1
    elif 2400 <= i <= 2799:
        rate[6] = 1
    elif 2800 <= i <= 3199:
        rate[7] = 1
    elif 3200 <= i:
        flag += 1
color_count = rate.count(1)
if flag:
    ans = [max(1, color_count),color_count + flag]
    print(* ans)
else:
    ans = [color_count, color_count]
    print(* ans)



Measured memory_bytes: 3316
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<string>
#include<math.h>
#include<stdlib.h>
#include<time.h>
#include<map>
#include<queue>
#include<set>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
int n,l,t,x[110000],w[110000],wei;
int main(){
	scanf("%d%d%d",&n,&l,&t);
	fo(i,1,n){
		scanf("%d%d",&x[i],&w[i]);
		if (w[i]==1) x[i]+=t;else x[i]-=t;
		wei+=x[i]/l;
		x[i]%=l;
		if (x[i]<0){
			wei--;
			x[i]+=l;
		}
	}
	sort(x+1,x+n+1);
	wei%=n;
	fo(i,1,n) printf("%d\n",x[(wei+i-1+n)%n+1]);//!!! (wei+i)->1..n
	return 0;
}

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

int main(){
  int N;
  int a[200];
  int b[200] = {};
  cin >> N;
  for(int i=0;i<N;i++){
    cin >> a[i];
    while((a[i] > 1) && (a[i]%2 == 0)){
      a[i] = a[i] / 2;
      b[i] = b[i] + 1;
    }
  }
  sort(b,b+N);
  cout << b[0] << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, l, r) for(register int i = l; i < r; i++)
#define hrp(i, l, r) for(register int i = l; i <= r; i++)
#define rev(i, r, l) for(register int i = r; i >= l; i--)
#define pb push_back
#define int ll
#ifndef JOEON
#define D(...)
#define R(x, l)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
template<typename tn> inline tn next(void);
template<typename tn> inline ostream& operator << (ostream& os, const vector<tn>& v);
int a[5], b[5];
signed main(void)
{
	#ifdef JOEON
//		freopen("C:\\Users\\Joeon\\Desktop\\IN.txt", "r", stdin);
//		freopen("C:\\Users\\Joeon\\Desktop\\OUT.txt", "w", stdout);
	#endif
	ios::sync_with_stdio(false);
	cin.tie(0);
	int a, b, c, d;
	cin>>a>>b>>c>>d;
	bool turn = 1;
	while(a > 0 && c > 0)
	{
		if (turn) c -= b;
		else a -= d;
		turn = !turn;
	}
	if (turn) cout<<"No"<<endl;
	else cout<<"Yes"<<endl;
	return 0;
}
template<typename tn> inline tn next(void)
{
	tn k;
	cin>>k;
	return k;
}
template<typename tn> inline ostream& operator << (ostream& os, const vector<tn>& v)
{
	rep(i, 0, v.size()) os<<v[i]<<' ';
	return os;
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using Graph = vector<vector<int>>;
const int INF = 1e9 + 1;
const ll LLINF = 1e18;

int main() {
    int K;
    string S;
    cin >> S >> K;
    bool same = true;
    vector<int> cnt;
    int c = 1;
    for(int i = 0; i < S.length() - 1; ++i) {
        if(S[i] == S[i + 1])
            c++;
        else {
            same = false;
            if(c != 1)
                cnt.push_back(c);
            c = 1;
        }
    }
    cnt.push_back(c);
    int cn = 0;
    for(int i = 0; i < cnt.size(); ++i) {
        cn += cnt[i] / 2;
    }
    if(S[0] == S[S.length() - 1])
        c = (cnt[0] + cnt[cnt.size() - 1]) / 2 - cnt[0] / 2 -
            (cnt[cnt.size() - 1]) / 2;
    else
        c = 0;
    ll ans = 0;
    if(same)
        ans = S.length() * (ll)K / 2;
    else {
        ans = cn * (ll)K + c * (ll)(K - 1);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void)
{
	int n;
	char s[100];
	int c[5] = {0,0,0,0,0};
	scanf ("%d",&n);
	int i = 0;
	while (i < n)
	{
		scanf("%s",s);
		if (strcmp("AC", s) ==0)
			c[0]++;
		if (strcmp("WA", s) ==0)
			c[1]++;
		if (strcmp("TLE", s) ==0)
			c[2]++;
		if (strcmp("RE", s) ==0)
			c[3]++;
		i++;
	}
	printf("AC x %d\n",c[0]);
	printf("WA x %d\n",c[1]);
	printf("TLE x %d\n",c[2]);
	printf("RE x %d\n",c[3]);
	return (0);
}


Measured memory_bytes: 1732
#include<bits/stdc++.h>
#define ll long long
#define w cout 
#define e '\n'

using namespace std;

const int N = 1e6 + 5;

set<pair<int ,int > > ans;
int main(){
	ios::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0);
	int n; cin >> n;
	if(n % 2 == 0) {
		for(int i = 1; i <= n ; i ++) {
			for(int j = i + 1 ; j <= n ; j ++) {
				if(i + j != n + 1)
					ans.insert({i , j});
			}
		}
	}
	else {
	for(int i = 1 ; i <= n - 1 ; i ++) {
		for(int j = i + 1 ; j <= n - 1; j ++) {
			if(i != j && j != (n - i)) {
				ans.insert({i , j});
			}
		}
	}
	for(int i = 1 ; i <= n - 1; i ++)
		ans.insert({i , n});
}
	w << ans.size() << e;
	for(auto i : ans)
		w << i.first << " " << i.second << e;
}

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

int main() {
  string S;
  cin >> S;
 
  vector<char> s(S.size());
  for (int i = 0; i < S.size(); i++) {
    s.at(i) = S.at(i);
  }
  
  int a;
  for (int i = 0; i < S.size(); i++) {
    if (s.at(i) == 'A'){
      a = i;
      break;
    }
  }
  int z;
  for (int i = S.size()-1; i >= 0; i--) {
    if (s.at(i) == 'Z'){
      z = i;
      break;
    }
  }
  cout << z - a + 1 << endl;
}
      

Measured memory_bytes: 772
#include <bits/stdc++.h>
using namespace std;
int main(){
    int a,b,n,m,v[5],c=0;
    cin >> a >> b;
    n = a;
    
    while(n <= b){
        m = n;
        for(int i=0;i<5;i++) {
            v[i] = m%10;
            m /= 10;
        }
        
        if(v[0]==v[4]&&v[1]==v[3]) c++;
        n++;
    }
    
    cout << c << "\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long int
#define pb push_back
#define fi first
#define se second
#define ld long double
#define vi vector<vector<ll> >
using namespace std;
const int MOD=1000000007;
const int MOD2=15000007;
const ll MAX=9187201950435737471;
const int N=100005;
const int INF=1e17;
const long double PI=acos(-1);



void solve(int T){
    int n;
    cin>>n;
    string a,b,c="";
    cin>>a>>b;
    for(int i=0;i<n;i++){
        c+=a[i];
        c+=b[i];
    }
    cout<<c<<"\n";
}

int main() {
    fastio
    int T=1;
    //cin>>T;
    for(int i=1;i<=T;i++){
        solve(i);
        //if(i<T)cout<<"\n";
    }
    return 0;
}





Measured memory_bytes: 3544
def solve():
    dishes = list(map(int, open(0).read().split()))
    
    last = 0
    dt_max = 0
    for i in range(5):
        if dishes[i] % 10 != 0 and dt_max <= 10 - (dishes[i] - dishes[i] // 10 * 10):
            dt_max = 10 - (dishes[i] - dishes[i] // 10 * 10)
            last = i
    
    ans = 0
    for i in range(5):
        if i != last:
            if dishes[i] % 10 != 0:
                ans += 10 * (dishes[i] // 10 + 1)
            else:
                ans += dishes[i]
        else:
            ans += dishes[i]
    print(ans)


if __name__ == '__main__':
    solve()

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1e8

template <typename T>
struct Graph {
    int V, E;
    struct Edge {
        int from, to;
        T cost;
    };
    vector<vector<Edge>> edge;
    vector<vector<T>> dist;
    vector<Edge> es;

    Graph(int V, int E) : V(V), E(E) {
        edge.assign(V, vector<Edge>(0));
        dist.assign(V, vector<T>(0));
    }

    void input(bool is_direct, bool inputc, bool index0 = false) {
        int a, b;
        T c = 0;
        for (int i = 0; i < E; i++) {
            cin >> a >> b;
            if (inputc) cin >> c;
            if (!index0) a--, b--;
            edge[a].push_back((Edge){a, b, c});
            es.push_back((Edge){a, b, c});
            if (!is_direct) {
                edge[b].push_back((Edge){b, a, c});
                es.push_back((Edge){b, a, c});
            }
        }
        if (!is_direct) E *= 2;
    }

    void add_edge(int from, int to, T cost, bool is_direct) {
        edge[from].push_back({from, to, cost});
        es.push_back({from, to, cost});
        if (!is_direct) {
            edge[to].push_back({to, from, cost});
            es.push_back({to, from, cost});
            E++;
        }
        E++;
    }

    typedef pair<T, int> P;  // (first,second) := (最短距離,頂点番号)
    // 頂点rからの最小距離
    void dijkstra(int r = 0) {
        dist[r].assign(V, INF);

        priority_queue<P, vector<P>, greater<P>> que;
        que.push(P(0, r));
        dist[r][r] = 0;

        while (que.size()) {
            P p = que.top();
            que.pop();
            int v = p.second;
            if (dist[r][v] < p.first) continue;
            for (int i = 0; i < edge[v].size(); i++) {
                Edge e = edge[v][i];
                if (dist[r][v] + e.cost < dist[r][e.to]) {
                    dist[r][e.to] = dist[r][v] + e.cost;
                    que.push(P(dist[r][e.to], e.to));
                }
            }
        }
    }
};

int main() {
    int N, X, Y;
    cin >> N >> X >> Y;
    Graph<int> g(N, 0);
    unordered_map<int, int> mp;
    for (int i = 0; i < N - 1; i++) g.add_edge(i, i + 1, 1, false);
    g.add_edge(X - 1, Y - 1, 1, false);
    for (int i = 0; i < N; i++) g.dijkstra(i);
    for (int i = 0; i < N; i++)
        for (int j = i + 1; j < N; j++) {
            mp[g.dist[i][j]]++;
        }
    for (int k = 1; k <= N - 1; k++) cout << mp[k] << endl;
    return 0;
}

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

int main() {
    int n;
    scanf("%d", &n);
    string s;
    cin >> s;
    if (n < 3200) printf("red\n");
    else cout << s << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define rrep(i, n) for (int i = (int)n-1; i >= 0; --i)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
const int mod = 1e9+7;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;

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; }

__attribute__ ((constructor))
void init() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(10);
}

signed main(){
    vector<int> v(5);
    rep(i, 5) cin >> v[i];
    int ans = inf;
    sort(v.begin(), v.end());
    do{
        int now = 0;
        rep(i,5){
            if(now%10!=0){
                now = ((now + 10 - 1) / 10) * 10;
            }
            now += v[i];
        }
        chmin(ans, now);
    } while(next_permutation(v.begin(), v.end()));
        // N!の順列の全探索
        cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define rep1(i,n) for(int i=1;i<=(int)n;i++)
#define sp(n) cout << fixed << setprecision(n)
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; }
typedef long long ll;
using namespace std;
int main(void){
    int n;cin>>n;
    int rain=0;
    set<int> s;
    rep(i,n){
        int a;cin>>a;
        if(a<400)s.insert(0);
        else if(a<800)s.insert(1);
        else if(a<1200)s.insert(2);
        else if(a<1600)s.insert(3);
        else if(a<2000)s.insert(4);
        else if(a<2400)s.insert(5);
        else if(a<2800)s.insert(6);
        else if(a<3200)s.insert(7);
        else rain++;
    }
    int res1=max(1,(int)(s.size()));
    cout<<res1<<" ";
    int resm=s.size()+rain;
    cout<<resm<<endl;
}


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

using namespace std;

int main(){
  	int N, M;
  	cin >> N >> M;
  	vector<int> a(2*M), d(N);
  	for(int i=0;i<2*M;i++){
      	cin >> a[i];
      	d[a[i]-1]++;
    }
  	for(int i=0;i<N;i++) cout << d[i] << endl;
}

Measured memory_bytes: 3592
#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>;

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

  double x = (((n - m) * 100) + (m * 1900)) / pow(0.5, m);

  cout << x << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N=200010;
char s[N];
inline int gi() {
    int x=0,o=1;
    char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') o=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*o;
}
int main() {
    int n,k,t=0,p=0;
    cin>>n>>k;
    scanf("%s",s);
    for(int i=0;i<n;i++) s[i]-='A';
    for(int i=1;i<=n+n+n;i++) {
	--k;
	if(!(s[p]^t)) s[p]^=1;
	else t^=1,p=(p+1)%n;
	if(!k) break;
    }
    k%=2;
    if(k&&!(s[p]^t)) s[p]^=1;
    for(int i=0;i<n;i++) putchar('A'+(s[(p+i)%n]^t));
    return 0;
}

Measured memory_bytes: 640
require 'set'; require 'prime'
INF=Float::INFINITY
n = gets.chomp.to_i
a = gets.chomp.split.map(&:to_i)
b = gets.chomp.split.map(&:to_i)

sum = a.inject(:+)
bsum = b.inject(:+)
if sum < bsum
  puts -1
  exit
end

ans = 0
needsum = 0
amari = Array.new(n,0)
n.times do |i|
  if b[i] > a[i]
    needsum += b[i] - a[i]
    ans += 1
  else
    amari[i] = a[i] - b[i]
  end
end
amari.sort!.reverse!
#p [ans, needsum, amari]

amari_i = 0
while needsum > 0
  needsum -= amari[amari_i]
  amari_i += 1
end

puts ans + amari_i


Measured memory_bytes: 18980
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 1002
#define i197 1000000007

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P1;
typedef pair<int,int> Pi;
typedef pair<double,Pi> Pdi;
typedef pair<ll,int>Pli;
typedef pair<P1,ll> P2;
const ll INF=1000000000000000001;
struct edge{int to,cost;};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct Road{double cost;int a,b;};

ll a[100001];
int main() {

	ll n;
	ll total=1;

	cin>>n;

	rep(i,n){
		cin>>a[i];
	}
	int f=0;
	if(a[0]>a[1])f=1;
	if(a[0]==a[1])f=3;

	for(int i=1; i<n-1; i++){
		if(a[i]>a[i+1]&&f==0){
			total++;
			f=3;
		}else if(a[i]<a[i+1]&&f==1){
			total++;
			f=3;
		}else if(a[i]>a[i+1]&&f==3)f=1;
		else if(a[i]<a[i+1]&&f==3)f=0;
	}
	cout<<total<<endl;

	return 0;

}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1145141919810893364
typedef pair<int,int> PP;
typedef long long ll;
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; }
#define int ll
#define setdouble setprecision
#define REP(i,n) for(int i=0;i<(n);++i)
#define OREP(i,n) for(int i=1;i<=(n);++i)
#define RREP(i,n) for(int i=(n)-1;i>=0;--i)
#define GOODBYE cout << -1 << endl;return 0
#define MM <<" "<<
#define Endl endl
int Roundup(int a,int b){
    return (a+b-1)/b;
}

signed main(void){
    int N,D;
    cin >> N >> D;
    D=2*D+1;
    cout << Roundup(N,D) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define s second
#define f first
#define pb push_back
#define endl '\n'
using namespace std;


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

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;

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

	ll a,b,x;
	cin >> a >> b >> x;

	ll ans = b/x - (a-1)/x;
	if(!a && x != 1) ans++;

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 3596
from random import randint
import sys
input = sys.stdin.readline
INF = 9223372036854775808


def calc_score(D, C, S, T):
    """
    開催日程Tを受け取ってそこまでのスコアを返す
    コンテストi 0-indexed
    d 0-indexed
    """
    score = 0
    last = [0]*26  # コンテストiを前回開催した日
    for d, t in enumerate(T):
        last[t] = d + 1
        for i in range(26):
            score -= (d + 1 - last[i]) * C[i]
        score += S[d][t]
    return score


def update_score(D, C, S, T, score, ct, ci):
    """
    ct日目のコンテストをコンテストciに変更する
    スコアを差分更新する

    ct: change t 変更日 0-indexed
    ci: change i 変更コンテスト 0-indexed
    """
    new_score = score
    last = [0]*26  # コンテストiを前回開催した日
    prei = T[ct]  # 変更前に開催する予定だったコンテストi
    for d, t in enumerate(T, start=1):
        last[t] = d
        new_score += (d - last[prei])*C[prei]
        new_score += (d - last[ci])*C[ci]
    last = [0]*26
    for d, t in enumerate(T, start=1):
        if d-1 == ct:
            last[ci] = d
        else:
            last[t] = d
        new_score -= (d - last[prei])*C[prei]
        new_score -= (d - last[ci])*C[ci]
    new_score -= S[ct][prei]
    new_score += S[ct][ci]
    return new_score


def evaluate(D, C, S, T, k):
    """
    d日目終了時点での満足度を計算し，
    d + k日目終了時点での満足度の減少も考慮する
    """
    score = 0
    last = [0]*26
    for d, t in enumerate(T):
        last[t] = d + 1
        for i in range(26):
            score -= (d + 1 - last[i]) * C[i]
        score += S[d][t]

    for d in range(len(T), min(len(T) + k, D)):
        for i in range(26):
            score -= (d + 1 - last[i]) * C[i]
    return score


def greedy(D, C, S):
    Ts = []
    for k in range(5, 13):
        T = []  # 0-indexed
        max_score = -INF
        for d in range(D):
            # d+k日目終了時点で満足度が一番高くなるようなコンテストiを開催する
            max_score = -INF
            best_i = 0
            for i in range(26):
                T.append(i)
                score = evaluate(D, C, S, T, k)
                if max_score < score:
                    max_score = score
                    best_i = i
                T.pop()
            T.append(best_i)
        Ts.append((max_score, T))
    return max(Ts, key=lambda pair: pair[0])


def local_search(D, C, S, score, T):
    for k in range(4000):
        ct = randint(0, D-1)
        ci = randint(0, 25)
        ori = T[ct]
        new_score = update_score(D, C, S, T, score, ct, ci)
        T[ct] = ci
        # 差分更新がバグってそう
        if score < new_score:
            score = new_score
        else:
            T[ct] = ori
    return T


if __name__ == '__main__':
    D = int(input())
    C = [int(i) for i in input().split()]
    S = [[int(i) for i in input().split()] for j in range(D)]
    init_score, T = greedy(D, C, S)
    T = local_search(D, C, S, init_score, T)
    for t in T:
        print(t+1)


Measured memory_bytes: 85764
#include<bits/stdc++.h>
      using namespace std;
      #define ll long long
      #define pb push_back
      #define pll  pair <long long,long long>
      #define mp make_pair
      #define ss second
      #define ff first
      #define maa 1000000007
      #define endl '\n'
      #define ld long double
      #define all(x) x.begin(),x.end()
      ll  power(ll  i,ll  j)
      {
        if(j==0)
        return 1 ;
        ll t=power(i,j/2)%maa ;
        if(j%2==0)
        return (t%maa*t%maa)%maa ;
        else
        return ((t%maa*t%maa)%maa*(i%maa)%maa)%maa ;
      }
      bool is(ll  i)
      {
        if(i==1)
            return 0 ;
        ll  f=0 ;
        for(ll  j=2;j<=sqrt(i);j++)
        {
            if(i%j==0)
            {
                f=1 ;
                break ;
            }
        }
        return !f ;
      }
      int main()
      {

        /// 50-4
        /// freopen("input.txt","r",stdin);
        /// freopen("output.txt","w",stdout);
        ll n,wt ;
        cin>>n>>wt ;
        vector<ll>dp(wt+1) ;
        for(ll i=1;i<=wt;i++)
        dp[i]=-1 ;
        
        dp[0]=0 ;
        for(ll i=0;i<n;i++)
        {
            ll a,b ;
            cin>>a>>b ;
            for(ll w=wt-a;w>=0;w--)
            {
                if(dp[w]!=-1)
                {
                    dp[w+a]=max(dp[w+a],dp[w]+b) ;
                }
            }
            
        }
        ll ans=0 ;
        for(ll i=0;i<=wt;i++)
        ans=max(ans,dp[i]) ;
        
        cout<<ans<<endl ;
      
        
        
      }








Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <string>
#include <cstring>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b-1;i>=a;i--)
#define FI first
#define SE second
#define SI size()
#define MA(i,j) make_pair(i,j)
#define PA pair<int,int>
#define PF push_front
#define PB push_back
#define VE vector<int>
#define VP vector<PA>
#define LL long long
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
using namespace std;
//
const int INF=1e9+7;
int H,W;
char S[50][50];
int sx=0,sy=0;
int gx,gy;
int D[50][50];
int DX[4]={-1,0,1,0};
int DY[4]={0,-1,0,1};
int BFS(){
  queue<PA> que;
  FOR(i,0,H){
    FOR(j,0,W){
      D[i][j]=INF;
    }
  }
  que.push(MA(sx,sy));
  D[sx][sy]=0;
  while(que.size()){
    PA P=que.front();
    que.pop();
    if(P.FI==gx&&P.SE==gy){
      break;
    }
    FOR(i,0,4){
      int NX=P.FI+DX[i],NY=P.SE+DY[i];
      if(0<=NX&&NX<H&&0<=NY&&NY<W&&S[NX][NY]=='.'&&D[NX][NY]==INF){
        que.push(MA(NX,NY));
        D[NX][NY]=D[P.FI][P.SE]+1;
      }
    }
  }
  return D[gx][gy];
}
int main(){
  cin>>H>>W;
  int cnt=0;
  FOR(i,0,H){
    FOR(j,0,W){
      cin>>S[i][j];
      if(S[i][j]=='.'){
        cnt++;
      }
    }
  }
  gx=H-1;gy=W-1;
  if(BFS()==INF){
    cout<<-1<<endl;
  }else{
    cout<<cnt-BFS()-1<<endl;
  }
  return 0;
}


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

int main(){
  while(1){
    int t;
    string num;
    cin >> t >> num;
    if(t==0 && num=="0") break;

    int now=0;
    int same_ct=0;
    int small=1000000;
    vector<int> ans;

    //???????????????????????°????????°
    int len = num.size();
    //?????????????????????????????????????????§bitloop
    for(int i=0; i<(1<<(len-1)); ++i){
      vector<int> s;

      int st=0;
      //printf(" %2d:", i);
      for(int j=0; j<len-1; ++j){
        if(i>>j & 1){
          s.push_back(atoi(num.substr(st,j+1-st).c_str()));
          st=j+1;
        }
      }
      s.push_back(atoi(num.substr(st,len+1-st).c_str()));

      int tmp=0;
      for(int j=0; j<s.size(); ++j) tmp+=s[j];
      //printf("%5d\n", tmp);

      small = min(small, tmp);

      if(t<tmp) continue;
      if(now<tmp){
        ans.resize(s.size());
        for(int j=0; j<s.size(); ++j) ans[j]=s[j];
        now=tmp;
        same_ct=1;
      }
      else if(now==tmp) same_ct++;
    }

    //output
    if(small>t) printf("error\n");
    else if(same_ct>1) printf("rejected\n");
    else{
      printf("%d", now);
      for(int i=0; i<ans.size(); ++i) printf(" %d", ans[i]);
      printf("\n");
    }
  }
}

Measured memory_bytes: 1256
#include<iostream>
#include<queue>
#include<memory>
#include<map>
#include<set>
#include<unordered_map>
#include<array>
#include<vector>
#include<algorithm>
#include<list>
#include<limits>
#include<stdio.h>
#include<math.h>
#include<string>
#include<thread>

using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;
using lst = list<ll>;

const ll MOD = 1000000007;

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

	int A; cin >> A;
	int v = 0;
	int ans = 0;

	for (int i = 1; i < N; ++i)
	{
		int H; cin >> H;

		if (A >= H)
		{
			ans = max(ans, ++v);
		}
		else
		{
			v = 0;
		}

		A = H;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main() {
    int a, b;
    while (cin >> a >> b) {
        long long ta = a, tb = b, tmp;
        while (ta != 0) {
            tmp = ta;
            ta = tb % ta;
            tb = tmp;
        }
        cout << tb << " " << a / tb * b << endl;
    }
    return 0;
}

Measured memory_bytes: 1156
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define all(v) v.begin(),v.end()
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
template<class T> void chmin(T &a,const T &b){if(a>b) a=b;}
template<class T> void chmax(T &a,const T &b){if(a<b) a=b;}

#include <functional>
#include <climits>

//SegmentTree<int> seg(N,[](int a,int b){return min(a,b);},INT_MAX);
template< typename T>
class SegmentTree{
private:
  void resize(int size){
      n=1;
      while(n<size) n*=2;
      tree.resize(2*n-1,def);
  }
public:

  using F = function<T(T,T)>;

  int n;
  vector<T> tree;
  F operation;
  T def;

  SegmentTree(){}
  SegmentTree(int size,F _operation,T _def):operation(_operation),def(_def){
    resize(size);
  }

  void embody(int size,F _operation,T _def){
    operation=_operation;
    def=_def;
    resize(size);
  }

  void initialize(const vector<T> &v){
    int size=v.size();
    resize(size);

    for(int i=0;i<size;i++) tree[i+n-1]=v[i];
    for(int i=n-2;i>=0;i--) tree[i]=operation(tree[2*i+1],tree[2*i+2]);
  }

  void update(int index,T value){
    index+=n-1;

    tree[index]=value;
    while(index>0){
      index=(index-1)/2;
      tree[index]=operation(tree[2*index+1],tree[2*index+2]);
    }
  }

  T query(int a,int b,int k=0,int l=0,int r=-1){//[a,b)
    if(r<0) r=n;

    if(r<=a||b<=l) return def;
    else if(a<=l&&r<=b) return tree[k];
    else{
      T lval=query(a,b,2*k+1,l,(l+r)/2);
      T rval=query(a,b,2*k+2,(l+r)/2,r);
      return operation(lval,rval);
    }
  }

  T get(int index){
      return tree[index+n-1];
  }

  int find(int x,int k=0,int l=0,int r=-1){// a[0]+...+a[i]>=x (i:minimal)
    if(r<0) r=n;
    if(tree[k]<x) return -1;
    if(r-l==1) return k-(n-1);
    if(tree[2*k+1]>=x) return find(x,2*k+1,l,(l+r)/2);
    else return find(x-tree[2*k+1],2*k+2,(l+r)/2,r);
  }

  //right -> change vl to vr   (notice doesn't contain b. range [a,b))
  int find_left(int a,int b,T x,int k=0,int l=0,int r=-1){// max(a[a],...,a[i])>=x (i:minimal)
      if(r<0) r=n;
      if(tree[k]<x||r<=a||b<=l) return -1;
      if(r-l==1) return k-(n-1);
      int vl=find_left(a,b,x,2*k+1,l,(l+r)/2);
      if(vl>=0) return vl;
      return find_left(a,b,x,2*k+2,(l+r)/2,r);
  }
};

const int L=3e5;

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

  int N,K;
  cin>>N>>K;
  vector<int> A(N);
  rep(i,N) cin>>A[i];

  SegmentTree<int> seg(L+10,[](int a,int b){return max(a,b);},0);
  rep(i,N){
    int l=max(0,A[i]-K);
    int r=min(L,A[i]+K);
    int res=seg.query(l,A[i]+1);
    chmax(res,seg.query(A[i]+1,r+1));

    seg.update(A[i],res+1);
  }

  cout<<seg.query(0,L+10)<<endl;

  return 0;
}


Measured memory_bytes: 8476
N = int(input())
A = list(map(int,input().split()))
B = [A[i]-i-1 for i in range(N)]
B.sort()
C = sorted(B,reverse = True)
s = 0
for i in range(N):
    if B[i] > C[i]:
        s += B[i]-C[i]
print(s)

Measured memory_bytes: 26836
s = input().split()

A = int(s[0])
B = int(s[1])
C = int(s[2])
D = int(s[3])

while(True):
  C -= B
  if (C <= 0):
    print('Yes')
    break
  A -= D
  if (A <= 0):
    print('No')
    break

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

int main()
{
    string s;
    int cnt[26] = {0};
    
    while (getline(cin, s)) {
        for (int i = 0; i < s.size(); i++) {
            if (isupper(s[i])) cnt[tolower(s[i])-'a']++;
            else cnt[s[i]-'a']++;
        }
    }
    
    for (int i = 0; i < 26; i++) {
        cout << char(i+'a') << " : " << cnt[i] << endl;
    }
}



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

using namespace std;

struct dsu {
    vector<int> par;
    vector<int> sz;
    dsu(int n) {
        par.resize(n);
        sz.assign(n,1);
        for (int i =0;i<n;i++) par[i] = i;
    }
    int root(int a) {
        return par[a] = par[a] == a ? a : root(par[a]);
    }
    void unite(int a, int b) {
        int ra = root(a);
        int rb = root(b);
        if (ra != rb) {
            sz[rb] = sz[ra] + sz[rb];
            par[ra] = rb;
        }
    }
};

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

    int N,M,K;
    cin>>N>>M>>K;

    vector<int> adj(N, 0);

    dsu s(N);

    for (int i=0;i<M;i++) {
        int a,b;
        cin>>a>>b;
        a--;b--;
        adj[a]++;
        adj[b]++;
        s.unite(a,b);
    }

    vector<int> res(N);
    for (int i=0;i<N;i++) {
        res[i] = s.sz[s.root(i)] - adj[i] - 1;
    }

    for (int i = 0; i < K; i++) {
        int a,b;
        cin>>a>>b;
        a--;b--;
        if (s.root(a) == s.root(b)) {
            res[a]--;
            res[b]--;
        }
    }

    for (int i=0;i<N;i++) {
        cout<<res[i]<<" ";
    }
    cout<<endl;

    return 0;
}

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

typedef long long LL;

const int N = 2010;
const LL mod = 924844033;

int n, k;

bool vis[N][2], st[N << 1];
int cnt;

LL f[N << 1][N][2];
LL fac[N];

int main()
{
	scanf("%d %d", &n, &k);
	st[1] = 1;
	for (int i = 1; i <= n; ++ i)
	{
		for (int j = 0; j <= 1; ++ j)
		{
			if (vis[i][j]) continue;
			for (int x = i, y = j; x <= n; x += k, y ^= 1)
				vis[x][y] = 1, ++ cnt;
			st[cnt + 1] = 1;
		}
	}
	f[0][0][0] = 1;
	for (int i = 1; i <= n << 1; ++ i)
	{
		for (int j = 0; j <= i >> 1; ++ j)
		{
			f[i][j][0] = (f[i - 1][j][0] + f[i - 1][j][1]) % mod;
			if (!st[i] && j) f[i][j][1] = f[i - 1][j - 1][0];
		}
	}
	fac[0] = 1;
	for (int i = 1; i <= n; ++ i)
		fac[i] = fac[i - 1] * i % mod;
	LL ans = 0;
	for (int i = 0; i <= n; ++ i)
		(ans += (i & 1 ? - 1 : 1) * (f[n << 1][i][0] + f[n << 1][i][1]) % mod * fac[n - i] % mod + mod) %= mod;
	printf("%lld\n", ans);
}

Measured memory_bytes: 124032
#include <bits/stdc++.h>
#define int long long int
#define ii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
using namespace std;
#define MOD 998244353
#define output(x) for (auto a:x) cout<<a<<" ";cout<<endl;
#define output2(x) for (auto a:x) cout<<a.fi<<" "<<a.se<<endl;
 
int power(int x,int y,int mod) 
{ 
 	int ret = 1;
 	x = x % mod;
 	while (y){
 		if(y&1) ret = (ret*x)%mod;
 		y = y>>1;
 		x = (x*x)%mod;
    } 
    return ret%mod; 
}

int isprime(int x)
{
	for (int i=2;i*i<=x;i++)
		if (x%i==0) return 0;
	return 1;
}

void solve()
{	
	
	int n,k;
	cin>>n>>k;
	vector<int> inp(n);
	for (auto &x:inp){
		cin>>x;
	}
	set<int> vis;
	int cyc = 0;
	int i=0;
	k--;
	for (;k;k--){
		if (vis.find(i)==vis.end()){
			vis.insert(i);
		}
		else break;
		i = inp[i] - 1;
	}
	vis.clear();

	for (;k;k--){
		if (vis.find(i)==vis.end()){
			vis.insert(i);
		}
		else break;
		i = inp[i] - 1;
	}

	if (k!=0){
		k%=vis.size();
		vis.clear();
		for (;k;k--){
		if (vis.find(i)==vis.end()){
			vis.insert(i);
		}
		else break;
		i = inp[i] - 1;
	}
	}
	cout<<inp[i]<<endl;
}
 
 
signed main(){
	// int t;
	// cin>>t;
	// while (t--)	
	solve();	
 
}

Measured memory_bytes: 12224
#include<bits/stdc++.h>
#define INF            1e9
#define REP(i,n)       for(lint i=0,i##_len=(n);i<i##_len;++i)
#define REP1(i,n)      for(lint i=1,i##_len=(n);i<=i##_len;++i)
#define REPI(i,ini,n)  for(lint i=(ini),i##_len=(n);i<i##_len;++i)
#define REPR(i,n)      for(lint i=(n)-1;i>=0;--i)
#define REPR1(i,n)     for(lint i=(n);i>0;--i)
#define REPRI(i,ini,n) for(lint i=(ini)-1,i##_len=(n);i>=i##_len;--i)
#define REPC(i,obj)    for(auto i:obj)
#define R_UP(a,b)      (((a)+(b)-1)/(b))
#define ALL(obj)       (obj).begin(),(obj).end()
using namespace std;
using lint = long long;
template<typename T = lint>inline T in() { T x; cin >> x; return x; }
int binary_search_p(int first_w, int last_w, int k, int min_w, int max_w, const vector<int>&w)
{
	auto get_minimum_k = [&w](int p_candidate)
	{
		int result = 1;
		int temp = 0;
		REPC(i, w)
		{
			if (temp + i <= p_candidate)temp += i;
			else
			{
				result++;
				temp = i;
			}
		}
		return result;
	};
	int p_candidate = first_w + (last_w - first_w) / 2;
	int min_k = get_minimum_k(p_candidate);
	if (first_w > last_w)
	{
		int result;
		for (int i = max(p_candidate, max_w);; i++)
		{
			int minimum_k = get_minimum_k(i);
			if (minimum_k <= k)return i;
		}
	}
	if (min_k <= k)
	{
		return  binary_search_p(first_w, p_candidate - 1, k, min_w, max_w, w);
	}
	else if (min_k > k)
	{
		return  binary_search_p(p_candidate + 1, last_w, k, min_w, max_w, w);
	}
}
signed main()
{
	int n = in(), k = in();
	vector<int>w(n);
	int min_w = 10001, max_w = -1, sum_w = 0;
	REPC(&i, w)
	{
		i = in();
		if (min_w > i)min_w = i;
		if (max_w < i)max_w = i;
		sum_w += i;
	}
	cout << binary_search_p(min_w, sum_w, k, min_w, max_w, w) << endl;
}


Measured memory_bytes: 3112
n = int(input())
spList = []
for i in range(n):
  a = list(input().split())
  spList.append([i+1, a[0], int(a[1])])
spList.sort(key=lambda x: -x[2])
spList.sort(key=lambda x: x[1])
for i in spList:
  print(i[0])

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

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = std::int64_t;
using P = std::tuple<int,int>;

template <typename T>
std::tuple<T, T, T> extgcd(T a, T b){
    T s1 = 1, t1 = 0, s2 = 0, t2 = 1;
    while(b != 0){
        std::tie(s1, t1, s2, t2) = std::make_tuple(s2, t2, s1 - (a / b) * s2, t1 - (a / b) * t2);
        std::tie(a, b) = std::make_tuple(b, a % b);
    }
    return std::make_tuple(s1, t1, a);
}

template <typename T>
T mod_expt(T a, std::int64_t n, T mod){
    T power {1};
    while(n > 0){
        if(n & 1){power = power * a % mod;}
        a = a * a % mod;
        n >>= 1;
    }
    return power;
}

// 注意: a と mod が互いに素である必要がある
template <typename T>
T mod_inverse(T a, T mod){
    T b;
    std::tie(b, std::ignore, std::ignore) = extgcd(a, mod);
    if(b < 0){b += mod;}
    return b;
}

const ll MOD = 1'000'003;
int Q;
ll X, D, N;
ll fact[1'000'100], inv_fact[1'000'100];

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

    fact[0] = 1;

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

    inv_fact[MOD-1] = mod_inverse(fact[MOD-1], MOD);

    for(int i=MOD-1;i>0;--i){
        inv_fact[i-1] = inv_fact[i] * i % MOD;
    }

    std::cin >> Q;

    for(int i=0;i<Q;++i){
        std::cin >> X >> D >> N;

        ll res;

        if(D == 0){
            res = mod_expt<ll>(X, N, MOD);
        }else{
            ll a = X * mod_inverse(D, MOD) % MOD;
            
            if(a + N > MOD){
                res = 0;
            }else{
                res = fact[a+N-1] * inv_fact[a-1] % MOD * mod_expt(D, N, MOD) % MOD;
            }
        }

        std::cout << res << std::endl;
    }
}


Measured memory_bytes: 16512
//inlclude before define 
#define _USE_MATH_DEFINES

//include
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<type_traits>
#include<numeric>
#include<assert.h>
//#include<deque>
#include<iomanip>
#include<set>
#include<tuple>
#include<map>

using namespace std;

//typedef
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<char> VC;
typedef pair<int, int> P1;
typedef long long int ll;

//define
#define INF 1e9
#define NUM 1000000007
#define all(x) begin(x),end(x)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define REP(i,a,b) for(int i=int(a);i<int(b);i++)
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))

/*ll gcd(ll a, ll b) {
	if (b == 0) return a;
	else return gcd(b, a%b);
}


ll lcm(ll a,ll b) {
	ll g = gcd(a, b);
	return a * b / g;
}*/

int main() {
	int a, b;
	string s;
	cin >> a >> b >> s;
	bool flag = true;
	if (s[a] != '-') {
		flag = false;
	}

	rep(i, s.size()) {
		if (i == a) {
			continue;
		} else if (!isdigit(s[i])) {
			flag = false;
		}
	}

	if (flag)cout << "Yes" << endl;
	else cout << "No" << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;

void Main() {
  ll n,x;
  cin >> n >> x;
  int a[n];
  rep(i,n) R a[i];
  sort(a,a+n);
  int ans=0;
  rep(i,n) {
    if(x>=a[i]) {
      ans++;
    }
    x-=a[i];
  }
  if(ans==n&&x) ans--;
  pr(ans);
}

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


Measured memory_bytes: 892
array  = [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(input())
k -= 1

print(array[k])

Measured memory_bytes: 3060
import collections 
n=input()
a=tuple(map(int,input().split()))
c=collections.Counter(a)
b=sorted(list(set(a)))[::-1]
ans,count=0,0
for i in b:
  if c[i]>3 and ans==0:
    print(i**2)
    exit()
  if c[i]>1:
    ans=ans*i if ans>0 else i
    count+=1
    if count==2:
      print(ans)
      exit()
print(ans)

Measured memory_bytes: 20644
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
#define int long long int

signed main(){
    int n;
    cin >> n;
    int result = 1;
    for(int i=1;i<=n;i++){
        result *= i;
        result %= 1000000007;
    }
    cout << result << endl;
}

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

using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

typedef pair<int, int> Pi;
typedef tuple<int, int, int> Ti;
typedef vector<int> vint;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int n;
  cin >> n;
  vint d(n);
  map<int, int> mp;
  rep(i, n) {
    cin >> d[i], mp[d[i]]++;
  }
  int m;
  cin >> m;
  vint t(m);
  bool flag = true;
  rep(i, m) {
    cin >> t[i];
    if(!mp.count(t[i]) || mp[t[i]] == 0) flag = false;
    mp[t[i]]--;
  }
  cout << (flag ? "YES" : "NO") << endl;


  return 0;
}


Measured memory_bytes: 15872
<?php

class Scanner
{
    private $arr = [];
    private $count = 0;
    private $pointer = 0;

    public function next()
    {
        if ($this->pointer >= $this->count) {
            $str = trim(fgets(STDIN));
            $this->arr = explode(" ", $str);
            $this->count = count($this->arr);
            $this->pointer = 0;
        }
        $result = $this->arr[$this->pointer];
        $this->pointer++;
        return $result;
    }

    public function hasNext()
    {
        return $this->pointer < $this->count;
    }

    public function nextInt()
    {
        return (int)$this->next();
    }

    public function nextDouble()
    {
        return (double)$this->next();
    }
}

class out
{
    public static function printIn($str = "")
    {
        echo $str . PHP_EOL;
    }
}

$sc = new Scanner;

$s = $sc->next();
$t = $sc->next();
$s = str_split($s);
$t = str_split($t);
sort($s);
rsort($t);

$s =  implode($s);
$t =  implode($t);

if($s < $t){
    echo 'Yes';
}else {
    echo 'No';
}

Measured memory_bytes: 4728
n=int(input())
t,a=map(int,input().split())
h=list(map(int,input().split()))
ans=0
x=10**9
for i in range(n):
    temp=abs(a-(t-h[i]*0.006))
    if temp < x:
        x=temp
        ans=i+1
print(ans)

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

int dp[100001];
set<int> s;

int main() {

    s.insert(1);
    dp[1] = 1;

    for(int i=6; i<=100000; i*=6){
        dp[i] = 1;
        s.insert(i);
    }

    for(int i=9; i<=100000; i*=9){
        dp[i] = 1;
        s.insert(i);
    }

    for(int i=1; i<=100000; i++){
        for(set<int>::iterator itr = s.begin(); itr != s.end(); itr++){
            if(i - *itr >= 1){
                if(dp[i] != 0) {
                    dp[i] = min(dp[i], dp[i - *itr] + 1);
                }
                else{
                    dp[i] = dp[i - *itr] + 1;
                }
            }
        }
    }

    int n;
    cin >> n;

    cout << dp[n] << endl;



    return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<utility>
#include<cmath>
#include<climits>
#include<queue>
#include<stack>
#include<numeric>
#include<set>
#include<iomanip>
#include<map>
using namespace std;


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


int main(){
  int n, d;
  cin >> n >> d;
  int ans = 0;
  int now = 0;
  while(true){

    if(now + 2 * d + 1 > n){
      break;
    } else {
      now += 2 * d + 1 ;
      ans ++;
    }
  }
  if(now - n != 0) ans++;

  cout << ans << endl;


}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<cmath>
#include<ctime>
#include<cstring>
#define yyj(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout);
#define llg long long
#define maxn 1001
using namespace std;
string a,b; llg la,lb;
int main()
{
	//yyj("a");
	cin>>a;
	llg ans=0;
	b="CODEFESTIVAL2016";
	for (llg i=0;i<=15;i++) if (a[i]!=b[i]) ans++;
	cout<<ans;
    return 0;
}


Measured memory_bytes: 256