akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <climits>
using namespace std;

bool comp(pair<int, string> a, pair<int, string> b){
    if(a.first != b.first) return a.first > b.first;
    else return a.second < b.second;
}

int main(){
    vector<int> vt;

    long int n,total = 0;
    cin >> n;

    for(int i = 0;i < n; ++i){
        int a;
        cin >> a;
        vt.push_back(a);
        total += a;
    }

    int m;
    cin >> m;
    vector<pair<int,int> > v;

    for(int i = 0; i < m; ++i){
        int j,x;
        cin >> j >> x;
        v.push_back(make_pair(j,x));
    }
    for(int i = 0; i < m; ++i){
        cout << total - vt[v[i].first - 1] + v[i].second << endl;

    }

}

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

int main() {
    int A,B,C;
    cin >>A >> B >> C;
    bool flag=true;
    flag=(A<C&&C<B)||(A>C&&C>B);
    if(flag) cout<<"Yes"<<endl;
    else cout << "No"<<endl; 

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = (A); I < (B); ++I)
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //ai>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //ai>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define REV(x) (reverse(x.begin(),x.end())) //reverse
#define TO(x,t,f) ((x)?(t):(f))
#define CLR(mat) memset(mat, 0, sizeof(mat))
#define FILV(x,a) fill(x.begin(),x.end(),a)
#define FILA(ar,N,a) fill(ar,ar+N,a)
#define NEXTP(x) next_permutation(x.begin(),x.end())
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;else return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
#define pb push_back
#define pri(aa) cout<<(aa)<<endl
#define mp(x,y) make_pair(x,y)
#define fi first
#define se second
const ll INF=1e9+7;
const ll N = 1000003;

class UnionFind{
public:
	vector<ll> par;
	//0-indexed
	void init(ll n = 1) {
		par.resize(n);
		for (ll i = 0; i < n; ++i) par[i] = i;
	}
	ll root(ll x = 1){
		if(par[x]==x)return x;
		else{
			return par[x] = root(par[x]);
		}
	}
	void unite(ll x = 1,ll y = 1){
		x = root(x);
		y = root(y);
		if(x==y)return;
		else par[x] = y;
	}
};

ll n,m,ans=0,coun=0;
vector<P> a;
vector<ll> b;
vector<bool> did;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	a.resize(n);
	did.resize(n);
	FOR(i,0,n){
		P p;
		cin>>p.fi;p.se=i;
		a[i]=p;
	}
	UnionFind uf;
	uf.init(n);
	FOR(i,0,m){
		ll x,y;cin>>x>>y;
		uf.unite(x,y);
	}
	set<ll> s;
	FOR(i,0,n){
		s.insert(uf.root(i));
	}
	if(s.size()==1){
		cout<<0<<endl;
		return 0;
	}
	SORT(a);
	FOR(i,0,n){
		if(!did[uf.root(a[i].se)]){
			ans+=a[i].fi;
			did[uf.root(a[i].se)]=true;
			coun++;
		}else{
			b.pb(a[i].fi);
		}
	}
	if((b.size()+coun)<2*(n-m-1)){
		cout<<"Impossible"<<endl;
		return 0;
	}
	ll i=0;
	while(coun!=2*(n-m-1)){
		ans+=b[i];
		++coun;
		++i;
	}
	cout<<ans<<endl;
	return 0;
}


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

signed main(void)
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int a;
	string s;
	cin >> a >> s;
	if (a >= 3200)cout << s;
	else cout << "red";
	return 0;
}

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

using namespace std;

int main(){
   int n;
   cin >> n;
   vector<int> S(n,0);
   for(int i=0;i<n;i++)cin >> S[i];
   int q;
   cin >> q;
   vector<int> T(q,0);
   for(int i=0;i<q;i++)cin >> T[i];
   int c=0;
   for(int i=0;i<q;i++){
       for(int j=0;j<n;j++){
           if(T[i]==S[j]){
               c++;
               break;
           }
       }
   }
   cout << c << endl;
  return 0;
}

Measured memory_bytes: 3108
#include <stdio.h>
#define I 1
#define V 5
#define X 10
#define L 50
#define C 100
#define D 500
#define M 1000
#define MAX 111

int main(void){
	char str[MAX];
	int seq[MAX];
	int counter;
	int i,n;
	while(scanf("%s",str) != EOF){
		counter = 0;
		for(i = 0; str[i] != 0; i++){
			switch(str[i]){
				case 'I':
					seq[i] = I;
				break;
				case 'V':
					seq[i] = V;
				break;
				case 'X':
					seq[i] = X;
				break;
				case 'L':
					seq[i] = L;
				break;
				case 'C':
					seq[i] = C;
				break;
				case 'D':
					seq[i] = D;
				break;
				case 'M':
					seq[i] = M;
				break;
			}
		}
		n = i;
		for(i = 0; i < n; i++){
			if(i == n-1){
				counter += seq[i];
			}else if(seq[i] >= seq[i+1]){
				counter += seq[i];
			}else{
				counter += (seq[i+1] - seq[i]);
				i++;
			}
		}
		printf("%d\n",counter);
	}

	return 0;
}

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

long long N, A[1 << 18], B[1 << 18], cnt1, cnt2, sum;
vector<int> X[1 << 18], Y[1 << 18];
vector<int> GX[1 << 18], GY[1 << 18];
bool usedx[1 << 18], usedy[1 << 18];

void dfs1(int pos) {
	if (usedx[pos] == true) return;
	usedx[pos] = true; cnt1++;
	for (int i = 0; i < GX[pos].size(); i++) dfs1(GX[pos][i]);
}

void dfs2(int pos) {
	if (usedy[pos] == true) return;
	usedy[pos] = true; cnt2++;
	for (int i = 0; i < GY[pos].size(); i++) dfs2(GY[pos][i]);
}

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> A[i] >> B[i];
		X[A[i]].push_back(B[i]);
		Y[B[i]].push_back(A[i]);
	}
	for (int i = 0; i <= 100000; i++) {
		sort(X[i].begin(), X[i].end());
		for (int j = 0; j < (int)X[i].size() - 1; j++) {
			GY[X[i][j]].push_back(X[i][j + 1]);
			GY[X[i][j + 1]].push_back(X[i][j]);
		}
	}
	for (int i = 0; i <= 100000; i++) {
		sort(Y[i].begin(), Y[i].end());
		for (int j = 0; j < (int)Y[i].size() - 1; j++) {
			GX[Y[i][j]].push_back(Y[i][j + 1]);
			GX[Y[i][j + 1]].push_back(Y[i][j]);
		}
	}
	for (int i = 1; i <= N; i++) {
		if (usedx[A[i]] == true || usedy[B[i]] == true) continue;
		cnt1 = 0; dfs1(A[i]);
		cnt2 = 0; dfs2(B[i]);
		sum += 1LL * cnt1 * cnt2;
	}
	cout << sum - N << endl;
	return 0;
}

Measured memory_bytes: 36352
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int x=0,y=0;
    int t=0;
    int a,b,c;
    for(int i=1;i<=n;i++)
    {
        cin>>c>>a>>b;
        if(abs(x-a)+abs(y-b)>c-t)
        {
            cout<<"No";
            return 0;
        }
        if((abs(x-a)+abs(y-b))%2==0 &&(c-t)%2==1)
        {
            cout<<"No";
            return 0;
        }
        if((abs(x-a)+abs(y-b))%2==1 &&(c-t)%2==0)
        {
            cout<<"No";
            return 0;
        }
        x=a;
		y=b;
		t=c;
    }
    cout<<"Yes";
    return 0;
}

Measured memory_bytes: 256
/*
平均がaになるため, 各カードx[i]に-=aすると和を0にするに帰着
dp[i][j]: i枚以下のカードを選んだ時に和がjになる組み合わせの総数
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - x[i]]
ここで-=aしているため, x[i]は負の値も取りうるため, 
必然的にjも負の値を取りうる.
初期値はdp[0][0] = 1とすれば良い.
したがって, dp[MAXn][MAXv * 2]となるようにdpを設定し, 
dp[i][MAXv]が和が0になる組み合わせの総数とする.
したがって, dp[0][MAXv] = 1を初期値.
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define sc(x) scanf("%d",&x);
static const int MAX = 50;
int main(){
    int n, a;
    sc(n) sc(a)
    int x[n + 1];
    for (int i = 1; i <= n; i++) sc(x[i])
    for (int i = 1; i <= n; i++) x[i] -= a;
    /*
    dp[i][MAX*MAX+k]にはi枚以上選択した時の和が
    kになる組み合わせの総数が格納
    */
    vector<vector<ll>> dp(MAX + 1, vector<ll>(MAX*MAX*2 + 1, 0));
    for (int i = 0; i <= n; i++){
        for (ll j = 0; j <= 2*MAX*MAX; j++){
            if (i == 0 && j == MAX*MAX) dp[i][j] = 1;
            else if (i > 0 && j - x[i] >= 0 && j - x[i] <= 2*MAX*MAX){
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - x[i]];
            }else if (i > 0) dp[i][j] = dp[i - 1][j];
        }
    }
    /*
    k == 0の時は0枚選択した時の和が0になる
    組み合わせの数を1としているため,答え-1する
    */
    cout << dp[n][MAX*MAX] - 1 << endl;
    return 0;
}

Measured memory_bytes: 2304
// "header" {{{
#pragma GCC optimize("Ofast")

#include <cassert>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <tuple>
#include <iomanip>
#include <climits>
#include <cstdlib>

using namespace std;

#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define int int64_t
#define double long double
#define Fixed fixed << setprecision(10)
#define moke_pair make_pair

constexpr int INF = 0x3f3f3f3f;
constexpr int64_t LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int64_t mod1 = 1000000007;
constexpr int64_t mod2 = 998244353;

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

template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class T> using max_heap = priority_queue<T>;
template <class T,class U> using umap = unordered_map<T,U>;

inline int64_t updiv(int64_t n,int64_t d){ return ((n + d -1) / d); }
inline int square(int a){ return a * a; }

int gcd(int a,int b){ return b ? gcd(b,a % b) : a;}
int lcm(int a,int b){ return a / gcd(a,b) * b;}
// }}}

signed main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;
    vector<int> p(n+5);

    reps(i,n){
        cin >> p[i];
    }

    int res = 0;
    reps(i,n){
        if(p[i] == i){
            ++res;
            ++i;
        }
    }

    cout << res << '\n';

    return 0;
}

Measured memory_bytes: 1024
// Problem : A - αlphabet
// Contest : AtCoder - AtCoder Beginner Contest 171
// URL : https://atcoder.jp/contests/abc171/tasks/abc171_a?lang=en
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=1;i<=(int)n;i++)
#define REP(i,n) for(int i=0;i<(int)n;i++)
#define ll long long
#define mod 1000000007
int lcm(int x,int y){
	return x/__gcd(x,y)*y;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    char c;
    cin>>c;
    if(isupper(c)){
    	cout<<'A'<<endl;
    }else{
    	cout<<'a'<<endl;
    }
    return 0;
}


Measured memory_bytes: 3644
//#pragma GCC optimize(2)
// Happy TLE and WA every day!
// by: zxb the vegetable chicken
#include<bits/stdc++.h>
#define mp              make_pair
#define rep(i,n)        for(int i = 0; i < n; i++)
#define foreach(i,c)    for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define BINF            0x7fffffff
#define INF             0x3f3f3f3f
#define LINF            4557430888798830399
#define END(s)          {cout<<s; return 0;}
#define CON(s)          {cout<<s; continue;}
#define BRE(s)          {cout<<s; break;}
#define pb              push_back
#define All(a)          a.begin(), a.end()  //with A in CAPITAL!!!
#define sz(a)           (int)a.size()
#define F               first
#define S               second
#define Time            clock()/CLOCKS_PER_SEC
//#define usingFiles
using namespace std;

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

inline bool Read(int& x){
	x = 0;
	int c;
	int sign = 1;
	while( (c = getchar()) < '0' || c > '9' ) if(c == '-') sign = -1;
	x = c ^ '0';
	while( (c = getchar()) >= '0' && c <= '9' ) x = (x<<3) + (x<<1) + (c ^ '0');
	x *= sign;
	return 1;
}

inline bool Write(int x){
	if(x >= 10) Write(x / 10);
	putchar(x % 10 + '0');
	return 1;
}

const int rp = 666666;
const bool debug = 1;
const bool I_good_vegetable_a = 1;

string s;

signed main(){
	ios::sync_with_stdio(false);
	#ifdef usingFiles
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif
	cin >> s;
	rep(i, s.size() + 1){
		for(int j = i; j < s.size() + 1; j++){
			if(s.substr(0, i) + s.substr(j, s.size() - j) == "keyence"){
				cout << "YES\n";
				return 0;
			}
		}
	}
	cout << "NO\n";
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <map>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#include <list>
#include <numeric>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <math.h>
#include <stack>
#include <climits>
#include <bitset>

using namespace std;
typedef long long ll;

//最小公倍数
ll gcd(ll x, ll y) {
  ll tmp = 0;
  if (x < y){
    tmp=x;
    x=y;
    y=tmp;
  }
  while (y > 0) {
    ll r = x % y;
    x = y;
    y = r;
  }
  return x;
}

//最大公倍数
ll lcm(ll x,ll y){
  return x/gcd(x,y)*y;
}

//階乗
ll kaijo(ll k){
    ll sum = 1;
    for (ll i = 1; i <= k; ++i)
    {
        sum *= i;
        sum%=1000000000+7;
    }
    return sum;
}

//for(int i = ; i < ; i++){}


int main(){
  int n,m;
  cin>>n>>m;
  vector<int> v(n,0);
  for(int i = 0; i < m; i++){
    int a,b;
    cin>>a>>b;
    v[a-1]++;
    v[b-1]++;
  }
  for(int i = 0; i < n; i++){
    cout<<v[i]<<endl;
  }
  return 0;
}

  



Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = Integer.parseInt(scan.next());
        int m = Integer.parseInt(scan.next());

        long[] a = new long[m];
        for (int i = 0; i < m; i++) {
            a[i] = Integer.parseInt(scan.next());
        }
        scan.close();

        long sum = 0;
        for (int i = 0; i < m; i++) {
            sum += a[i];
        }

        if (n >= sum) {
            System.out.println(n - sum);
        } else {
            System.out.println(-1);
        }

    }

}


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

typedef long long ll;
const ll MOD = 1000000007;

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<int> a(n), b(n), c(n);
    for (int i = 0; i < n; i++) cin >> a[i] >> b[i] >> c[i];
    int t1 = a[0], t2 = b[0], t3 = c[0];
    for (int i = 1; i < n; i++) {
        int s1 = max(t2, t3) + a[i];
        int s2 = max(t1, t3) + b[i];
        int s3 = max(t2, t1) + c[i];
        t1 = s1;
        t2 = s2;
        t3 = s3;
    }
    cout << max(max(t1, t2), t3);

    return 0;
}

Measured memory_bytes: 1408
#ifdef __GNUC__
#pragma GCC diagnostic ignored "-Wunused-result"
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <sstream>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <vector>

using namespace std;

typedef long long LL;
typedef long double LD;
typedef pair<LL, LL> II;
typedef pair<LL, II> III;
typedef priority_queue<III, vector<III>, greater<>> Queue;
static const LL INF = 1LL << 60;

LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }
LL lcm(LL a, LL b) { return (a / gcd(a, b)) * b; }

#if 0
	auto possible = [&](LL t) {

		return false;
	};
	LL left = 1, right = 1000000000;
	while (right - left > 1) {
		LL mid = (left + right) / 2;
		if (possible(mid)) {
			left = mid;
		} else {
			right = mid;
		}
	}
#endif

void solve(long long N, long long X, long long M) {
	LL ans = 0;
	LL x = X;
	vector<LL> prev(M + 1, -1), sum(M + 1);
	LL i;
	for (i = 0; i < min(N, 10000LL); ++i) {
		ans += x;
		x = x * x % M;
	}
	for (; i < N; ++i) {
		ans += x;
		x = x * x % M;
		if (prev[x] >= 0) {
			LL t = i - prev[x];
			LL r = (N - i - t) / t;
			LL diff = ans - sum[x];
			if (r > 0) {
				ans += diff * r;
				i += t * r;
			}
		}
		sum[x] = ans;
		prev[x] = i;
	}
	cout << ans << endl;
}

int main() {
    long long N;
	std::cin >> N;
	long long X;
	std::cin >> X;
	long long M;
	std::cin >> M;
	solve(N, X, M);
	return 0;
}


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

using namespace std;


int main() {
    int a = 0, b = 0;
    cin >> a >> b;

    for (int i = 0; i < a; ++i) {
        for (int j = 0; j < b; ++j) {
            for (int c = 1; c <= 3; ++c) {
                if ((a * b * c) % 2 == 1) {
                    cout << "Yes" << endl;
                    return 0;
                }
            }
        }
    }

    cout << "No" << endl;
}

Measured memory_bytes: 3616
#include<stdio.h>
int main(void)
{
  char b;

  scanf("%c",&b);

  switch(b){
    case 'A':
    printf("T");
    break;

    case 'C':
    printf("G");
    break;

    case 'T':
    printf("A");
    break;

    case 'G':
    printf("C");
    break;
  }

  return 0;
}


Measured memory_bytes: 128
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int k = sc.nextInt();
		for (int i = a; i <= b; i++) {
			if (i - a <= k - 1 || b - i <= k - 1) {
				System.out.println(i);
			}
		}
		sc.close();
	}

}


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

using namespace std;

#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define pb push_back
#define endl '\n'
#define snd second
#define fst first
#define fastio cin.tie(NULL),cout.sync_with_stdio(true)

typedef long long int ll;
typedef unsigned long long int ull;
typedef vector <int> vi;
typedef pair <int, int> ii;

const int mod = 1e9 + 7;
const ll INF = (1LL<<50);
const double EPSILON = 0.001;
const int N = 1000005;
int main(){
	fastio;
	ll n, x, m;
	map<ll,ll> see;
	cin >> n >> x >> m;
	ll last = x, atual;
	while(true){
		atual = last*last % m;
		last = atual;
		see[atual]++;
		if(see[atual] == 3)break;
	}
	vector<ll> v1, v2;
	ll sum1 = 0, sum2 = 0, aux = 1;
	last = x;
	while(true){
		atual = last*last % m;
		last = atual;
		if(see[atual] == 3 and !aux)break;
		if(see[atual] == 3)aux = 0;
		if(see[atual] == 1)v1.pb(atual), sum1 += atual;
		else v2.pb(atual), sum2 += atual;
	}
	ll ans = x;
	n--;
	if(n < (ll)sz(v1)){
		for(int i = 0; i < n; i++)
			ans += v1[i];
	}else{
		n -= (ll)sz(v1);
		ans += sum1;
		if(n < (ll)sz(v2)){
			for(int i = 0; i < n; i++)
				ans += v2[i];
		}else{
			ans += sum2*(ll)(n/(ll)sz(v2));
			n %= (ll)sz(v2);
			for(int i = 0; i < n; i++)
				ans += v2[i];
		}
	}
	cout << ans << '\n';
	return 0;
}


Measured memory_bytes: 6912
#include <bits/stdc++.h>
using namespace std;
int N, M, K, S, P, Q, a, b, d1[111111], z[111111]; long long d2[111111]; vector<int> G[111111];
int main() {
	scanf("%d%d%d%d%d%d", &N, &M, &K, &S, &P, &Q);
	queue<int> que1;
	fill(d1, d1 + N, -1);
	for (int i = 0; i < K; i++) {
		scanf("%d", &a); a--; z[a] = 1;
		d1[a] = 0, que1.push(a);
	}
	for (int i = 0; i < M; i++) {
		scanf("%d%d", &a, &b); a--, b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	while (!que1.empty()) {
		int v = que1.front(); que1.pop();
		for (auto &e : G[v]) {
			if (d1[e] == -1) d1[e] = d1[v] + 1, que1.push(e);
		}
	}
	priority_queue<pair<long long, int> > que2; que2.push(make_pair(0, 0));
	fill(d2 + 1, d2 + N, 1LL << 60);
	while (!que2.empty()) {
		int v = que2.top().second; que2.pop();
		for (auto &e : G[v]) {
			if (z[e]) continue;
			long long f = d2[v] + (d1[e] <= S ? Q : P);
			if (d2[e] > f) d2[e] = f, que2.push(make_pair(-d2[e], e));
		}
	}
	cout << d2[N - 1] - (d1[N - 1] <= S ? Q : P) << endl;
	return 0;
}

Measured memory_bytes: 11664
n=int(input())
A=[[] for i in range(n)]
for i in range(n):
    x,l=map(int,input().split())
    A[i]=[x-l,x+l]
A=sorted(A, key=lambda x :x[1])
#print(A)

ans=0
last=-float("INF")
for i in range(n):
    if last<=A[i][0]:
        ans+=1
        last=A[i][1]

print(ans)


Measured memory_bytes: 26180
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int numbers[10],x;
    for(int i=0;i<10;i++){
        numbers[i]=0;
    }
    for(int i=0;i<4;i++){
        cin >> x;
        numbers[x]++;
    }
    if(numbers[1]>0 && numbers[9]>0 && numbers[7]>0 && numbers[4]>0){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
# union-findかな
# 蟻本によればunion-findは分割できないっぽいので、ちょっと違う? 
# 時刻を巻き戻して、橋なしから橋を建設することにすれば扱える

# 橋が崩落してA+B　がAとBに分かれたら、不便度はA*B増加する

n,m = map(int, input().split())

def find_root(x):
	if par[x] == x:
		return x
	else:
		par[x] = find_root(par[x])
		return par[x]

def unite(x, y):
	x = find_root(x)
	y = find_root(y)
	if(x == y):
		return 0

	if rank[x] < rank[y]:
		par[x] = y

		temp = size[x] * size[y]
		size[y] = size[x] + size[y]
	else:
		par[y] = x
		if (rank[x] == rank[y]):
			rank[x] += 11

		temp = size[x] * size[y]
		size[x] = size[x] + size[y]
	return temp



def is_same(x,y):
	return find_root(x) == find_root(y)

'''
par = list(n, 0)
rank = list(n, 0)
size = list(n, 1)
'''
# par = [0]*n
par = list(range(n))
rank = [0]*n
size = [1]*n

bridges = [list(map(int, input().split())) for _ in range(m)]
bridges = [[b[0]-1, b[1]-1] for b in bridges]

fuben_list = [0]*m
fuben = int(n * (n-1)/2)
fuben_list[-1] = fuben

for b in range(m-1,0, -1):
	# 最初の状態は1番目が崩れたあと：1番目を建設した後の状態は不要

	decr = unite(bridges[b][0] , bridges[b][1])
	fuben -= decr
	fuben_list[b-1] = fuben

# print(fuben_list)

for i in fuben_list:
	print(i)

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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using edge = pair<ll, P>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
using Graph = vector<vector<ll>>;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

#include "cpp-pyprint/pyprint.h"

#endif

ll dp[2005][2005];

void Main() {
    int N, M;
    cin >> N >> M;
    vector<ll> S(N), T(M);
    rep(i, N) cin >> S[i];
    rep(i, M) cin >> T[i];
    rep(i, N) {
        rep(j, M){
            if (S[i] == T[j]) {
                dp[i+1][j+1] += dp[i][j] + 1;
            }
            dp[i+1][j+1] += dp[i+1][j] + dp[i][j+1] - dp[i][j];
            if(dp[i+1][j+1] < 0){
                dp[i+1][j+1] += MOD;
            }
            dp[i+1][j+1] %= MOD;
        }
    }
    cout << dp[N][M] + 1 << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
}


Measured memory_bytes: 31616
#include<iostream>
using namespace std;
int main(){
	int a,b,c,d;
	cin>>a;
	
	if(a/100==1)
		b=9;
	else
		b=1;
	
	if((a%100)/10==1)
		c=9;
	else
		c=1;
	
	if(a%10==1)
		d=9;
	else
		d=1;
		
	cout<<b<<c<<d<<endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fastIO ios::sync_with_stdio(0), cin.tie(0)
#define endl '\n'

int main() {
	int n, x;
	cin >> n >> x;
	int dp[n+2];
	int l[n+2];
	int ans = 1;
	
	for(int i = 1; i<=n; i++)
		cin >> l[i];
	
	dp[1] = 0;
	
	for(int i = 2; i<=n+1; i++){
		dp[i] = dp[i-1] + l[i-1];
		if(dp[i] <= x) ans++;
	}
	
	cout << ans << endl;
	
	
	
	
	return 0;
}

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

fn main() {
    let n: usize = read();
    let mut a: Vec<i64> = Vec::new();
    let mut b: Vec<i64> = Vec::new();
    for _ in 0..n {
        a.push(read::<i64>());
        b.push(read::<i64>());
    }
    let mut d: Vec<(i64, i64, i64)> = vec![(0, 0, 0); n];
    for i in 0..n {
        d[i] = (a[i] + b[i], a[i], b[i]);
    }
    d.sort();
    let mut ans = 0;
    let mut ai = n;
    while ai > 0 {
        ans += d[ai-1].1;
        ai -= 1;
        if ai == 0 {
            break;
        }
        ans -= d[ai-1].2;
        ai -= 1;
    }
    println!("{}", ans);
}

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")
}


Measured memory_bytes: 12540
s = list(map(str, input()))
n = len(s)
sum = 0
for i in range(2 ** (n-1)):
  bag = []
  t = s[:]
  for j in range(n):
    if (i >> j) & 1:
      bag.append(j)   
  bag = sorted(bag, reverse=True)
  for k in range(len(bag)):
    t.insert(bag[k]+1, '+')
  #print(eval(''.join(t)))
  sum += eval(''.join(t))

print(sum)

Measured memory_bytes: 3064
#include<iostream>
#define rep(i,n) for(int i=0; i<(n); ++i)

int main(){
    int n,m; std::cin >> n >> m;
    int a, total=0;
    rep(i,m){
        std::cin >> a;
        total += a;
    }
    std::cout << (total > n ? -1 : n-total) << std::endl;
    return 0;
}

Measured memory_bytes: 3628
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <numeric>
using namespace std;
#define loop(i,N) for(ll (i)=0; (i)<(N);++(i))
struct _OMAZINAI_ { _OMAZINAI_() { std::ios::sync_with_stdio(false); std::cin.tie(0); } } __omazinai_instance__;
#define INF ((1LL<<61) + (1<<29))
#define YesNo(x) {std::cout << ((x)?"Yes":"No") << std::endl;}
#define YESNO(x) {std::cout << ((x)?"YES":"NO") << std::endl;}
#define OddEven(x) {std::cout << ((x)%2?"Odd":"Even") << std::endl;}
#define ODDEVEN(x) {std::cout << ((x)%2?"ODD":"EVEN") << std::endl;}
typedef long long int ll;
ll my_gcd(ll a, ll b) { return b ? my_gcd(b, a%b) : a; };
void _INPUT_IMPL_() {};
template <class T, class... Args> void _INPUT_IMPL_(T& dest, Args&... args) { cin >> dest; _INPUT_IMPL_(args...); }
void _OUTPUT_IMPL_() {};
template <class T, class... Args> void _OUTPUT_IMPL_(T dest, Args... args) { cout << dest << (sizeof...(Args) ? " " : ""); _OUTPUT_IMPL_(args...); }
#define in(type, ...) type __VA_ARGS__; _INPUT_IMPL_(__VA_ARGS__)
#define in_v(type, name, cnt) vector<type> name(cnt); loop(i, cnt) cin >> name[i];
#define sort_v(v) std::sort(v.begin(), v.end())
#define unique_v(v) v.erase(std::unique(v.begin(), v.end()), v.end()) //必ずソート後に実行
#define out(...) (_OUTPUT_IMPL_(__VA_ARGS__), std::cout<<std::endl)
#define set_fix(x) ((std::cerr<<std::fixed<<std::setprecision(x)),(std::cout<<std::fixed<<std::setprecision(x)))
//小さい方に寄る
#define space_op(x, y, a, b, c) ([](auto x_, auto y_, auto a_, auto b_, auto c_){if(x_<y_)return a_;if(x_>y_)return c_;return b_;}(x,y,a,b,c))
#define space_out(x, y, a, b, c) out(space_op(x, y, a, b, c))

// ^^^ Template ^^^ //


int main() {
	in(ll, A, B, K);
	ll t;
	for (t = A; t < B && t - A < K; ++t)
		out(t);
	for (t = max(t, B - K + 1); t <= B; ++t)
		out(t);
	return 0;
}


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

typedef long long ll;
#define all(x) (x).begin(), (x).end()  // sortなどの引数を省略
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define max3(x, y, z) max(x, max(y, z))
#define min3(x, y, z) min(x, min(y, z))

#ifdef _MSC_FULL_VER  //デバッグ出力
#define dout cout
#define debug() if (true)
#define check(x) std::cout << "★" << #x << "の値:" << (x) << endl
#define pass(x) std::cout << "☆" << x << endl
#else
#define dout \
  if (false) cout
#define debug() if (false)
#define check(x) \
  if (false) cout << "★" << #x << "の値:" << (x) << endl
#define pass(x) \
  if (false) cout << "☆" << x << endl
#endif

using namespace std;
int main(){
    int a,b;
    cin >> a;
    if(a>=30){
        cout << "Yes";
    }else{
        cout << "No";
    }
    return 0;
}
/*
//よく使うやつ
int N;
cin >> N;
vector<int> list(N);
rep(i,N) {
  cin >> list[i];
}
//配列(スタックとしても使える)
vector<int> list;
list.at(i)
vector<vector<int>> list(10, vector<int>(10));
//ソート クイックだからO(NlogN)
sort(all(list));
sort(all(list), greater<int>());

//配列の内容表示
dout << "====listの内容====\n";
for (int edp = 0; edp < N; edp++) dout << list[edp] << endl;
dout << "====ここまで====\n";


//配列の最小最大(Nは要素数)
*min_element(all(c))
*max_element(all(c))

//a[0]からa[N]を逆順にする(計算量はO(N))
reverse(all(a));
//listの末尾に要素を追加
list.push_back(10);
//listの末尾から要素を削除
list.pop_back();
//空ですか？
list.empty()



//キュー(待ち行列)
//定義
queue<int> a;
//追加
a.push(x);
//取る
a.pop();
//チェック
a.front()
//サイズ
a.size()
//空ですか
a.empty()



//優先度付きキュー※全部計算量がO(NlogN)あるので注意
// int 型の要素を持ち、最も小さい値を取り出す形の priority_queue を定義
priority_queue<int, vector<int>, greater<int>> Q1;
// double 型の要素を持ち、最も大きい値を取り出す形の priority_queueを定義
priority_queue<double, vector<double>, less<double>> Q2;
//追加
a.push(x);
//取る
a.pop();
//一番小さいの教えて下さい
a.top()
//サイズ
a.size()
//空ですか
a.empty()



//部分文字列
//添字3から5文字
s.substr(3,5)
//添字3から全部
s.substr(3)

//入れ替え
swap(a,b);



// int 型の番地に string 型の変数を記録する場合（2^31 要素の string型配列と同じような感じ）
map<int, string> mp;
for (auto itr =mp.begin(); itr != mp.end(); itr++) {
    //順番にマップを眺める。itr->firstでキー、itr->secondがバリュー
}

//ソート済みのaの中で初めてx以上になるインデックスを返す
lower_bound(all(a), x) - a

//next_permutation
do {
  //ここにパーテーションがくる
} while (next_permutation(s.begin(), s.end()));

//set
set<int> hoge;
hoge.insert(50);  //hogeに挿入。重複は無視される。
hoge.insert(20);  //内部は小さい順に並ぶ
hoge.erase(50);   //hogeから消し去る。
//40以上である最小の要素を指すイテレーターを返す。
//もちろんそんなものはないからEndが出力される
auto itr1 = Set.lower_bound(40);
if (itr1 == Set.end()) cout << "End" << endl;
else cout << (*itr1) << endl;

//pair
//たくさんつくる
vector<pair<int,string>> hoge(10);
//参照
hoge[0].first
sort(all(hoge), greater<pair<int, string>>());




*/


Measured memory_bytes: 3600
#include <iostream>
#include <iomanip>
#include <vector>
#include <array>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>

using namespace std;
using ll=long long int;

int main() {
    int n;
    cin >> n;
    double ans = 0;
    for (int i = 0; i < n; ++i) {
        double x;
        cin >> x;
        string u;
        cin >> u;
        if (u == "BTC") {
            x *= 380000;
        }
        ans += x;
    }

    cout << setprecision(20) << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<iostream>
#include<fstream>
#define ll long long
using namespace std;

int main(){
    int N, W;  cin >> N >> W;
    vector<int> w(N+1,0), v(N+1, 0);
    for(int i=1; i<=N; i++){
        cin >> w[i] >> v[i];
    }

    vector<vector<ll>> dp(N+1, vector<ll>(W+1, 0));
    for(int i=1; i<=N; i++) for(int j=0; j<=W; j++){
        dp[i][j] = dp[i-1][j];
        if(w[i] <= j){
            dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i]);
        }
    }

    ll ans = 0;
    for(int j=0; j<=W; j++){
        ans = max(ans, dp[N][j]);
    }
    cout << ans << endl;
}


Measured memory_bytes: 80256
from collections import OrderedDict
n = int(input())
d = {}
for i in range(n):
    s = input()
    if s in d:
        d[s] += 1
    else:
        d[s] = 1
d = OrderedDict(sorted(d.items()))
mx = 0
for v in d.values():
    mx = max(v, mx)
for k, v in d.items():
    if v == mx:
        print(k)


Measured memory_bytes: 110544
/*
 * FileName:     A
 * CreatedDate:  2020-03-28 20:59:35 +0900
 * LastModified: 2020-03-28 21:02:23 +0900
 */

#include <stdio.h>

int main(void){
    char S[6];
    scanf("%s",S);
    if(S[2]==S[3]){
        if(S[4]==S[5]){
            printf("Yes\n");
            return 0;
        }
    }
    printf("No\n");
    return 0;
}


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

int main(){
    int N;
    cin >> N;
    vector<int> P(N);
    vector<int> Q(N);
    vector<int> R(N);
    int i;
    int p=0,q=0,num=0;
    for(i=0;i<N;i++){
        cin >> P[i];
    }
    for(i=0;i<N;i++){
        cin >> Q[i];
        R[i] = i+1;
    }
    do{
        num++;
        if(P == R) 
            p = num;
        if(Q == R) 
            q = num;
    }while(next_permutation(R.begin(), R.end()));

    cout << abs(p-q) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include<vector>
#include <algorithm>
#include<cstdlib>
#include<set>
#include<math.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define rep(i,n) for(ll i=0;i<n;i++)

int main()
{
	int n;
	cin >> n;
	vector<int> w(n);
	int sum = 0;
	for (int i = 0; i < n; i++)
	{
		cin >> w[i];
		sum += w[i];
	}
	int ans = 1000000;
	int ss = 0;
	for (int t = 0; t < n; t++)
	{
		ss += w[t];
		if (max(sum - 2 * ss, 2 * ss - sum) < ans)
		{
			ans = max(sum - 2 * ss, 2 * ss - sum);
		}
	}

	cout << ans << "\n";

	return 0;
}

Measured memory_bytes: 3584
#include <iostream>
#include <algorithm>
#include <limits>
#include <vector>
#include <map>
#include <cmath>
#include <limits>
#include <iomanip>
#include <queue>
#include <string.h>
#include <bitset>

#define ll long long int
#define ld long double
#define rep(i,n) for(int i = 0;i < n;i++)
#define rep1(i,n) for(int i = 1;i < n;i++)
#define co(x) cout << x << endl
#define cosp(x) cout << x << " "
#define all(x) x.begin(),x.end()
#define allr(x) x.begin(),x.end(),greater<int>()
#define P pair<ll,ll>
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define INF 1ll << 60
#define PI 3.14159265359

using namespace std;

int main(){
	string a,b,c;
	cin >> a >> b >> c;
	if(a[a.size()-1] == b[0] && b[b.size()-1] == c[0]) cout << "YES" << endl;
	else cout << "NO" << endl;
	return 0;
}

Measured memory_bytes: 256
//g++  5.4.0

#include <bits/stdc++.h>
using namespace std;
const long double nax = 1e15L+1;
const int MAXN = 3001;
long double dp[MAXN][MAXN];
long double computeProb(long double *pheads,int n,int heads,int tails){
    long double &ans = dp[heads][tails];
    if(ans!=nax)
        return ans;
    if(n == 0)
        return ans = heads>tails?1:0;
    
    ans = pheads[n-1]*computeProb(pheads,n-1,heads+1,tails) + (1-pheads[n-1])*computeProb(pheads,n-1,heads,tails+1);
    return ans;
}

int main()
{
    int n;
    scanf("%d",&n);
    long double ans = 0;
    long double phead[n];//probability of getting head
   
    for(int i = 0;i<=n;i++)
        for(int j = 0;j<=(n+1)/2;j++)
                dp[i][j] =nax;
    for(int   i= 0;i<n;i++){
        scanf("%Lf",&phead[i]);
    }
    ans = computeProb(phead,n,0,0);
    /*
    int heads = (n+1)/2;
    int tails = n - heads;
    while(heads <= n){
          string p = string(heads,'h') + string((n-heads),'t');
          do{
                long double pr3 = 1;
                for(size_t i =0 ;i<p.length();i++)
                {
                    pr3 *= (p[i]=='h'?phead[i]:(1-phead[i]));
                }
                ans += pr3;
          }while(next_permutation(p.begin(),p.end()));
          ++heads;
    }
    */
    
   printf("%1.10Lf\n",ans);
    return 0;
}

Measured memory_bytes: 139776
#include<iostream>
#include<iomanip>
#include<stdio.h>

using namespace std;

int main()
{
    int a,b;
    double c;
    cin >> a >> b;
    c = 1.0 * a / b;
    cout << a / b << " ";
    cout << a % b << " "; 
    printf("%.8lf\n", c);
    return 0;
}


Measured memory_bytes: 3248
// D - Widespread
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define rp(i,n) for(int i=0;i<(n);++i)
#define roundup(a,b) (((a)+(b)-1)/(b))

int main(){
	int N,A,B; cin>>N>>A>>B;
	A -= B;//additional damage
	vector<int> H(N); rp(i, N) cin>>H[i];
	int ans = INT_MAX;
	int L = 0, R = 1e9+1;//[L,R), R: answer
	while(L < R){
		int t = (L + R)/2;//mid, number of basic attacks
		LL tb = (LL)t * B;
		LL at = 0;//number of additional atacks
		rp(i, N) if(H[i] > tb) at += roundup(H[i] - tb, A);
		if(t >= at) R = t;//mid
		else L = t + 1;//mid+1
	}
	cout<< R <<endl;
}

Measured memory_bytes: 640
A,B,K = map(int, input().split())
div_1 = []
div_res = []
for i in range(A+1):
    if i != 0 and A%i == 0:
        div_1.append(i)
for i in range(B+1):
    if i != 0 and B%i == 0 and (i in div_1):
        div_res.append(i)
div_res.reverse()
print(div_res[K-1])

Measured memory_bytes: 38384
def binary_search(l, t):
    left = 0
    right = len(l) - 1

    while left <= right:
        mid = (left + right)//2
        if l[mid] < t:
            left = mid + 1
        elif t < l[mid]:
            right = mid - 1
        else:
            return True

def main():
    n = int(input())
    s = list(map(int, input().split()))
    q = int(input())
    t = list(map(int, input().split()))

    cnt = 0
    for et in t:
        bl = binary_search(s, et)
        if bl:
            cnt += 1

    print(cnt)

if __name__ == '__main__':
    main()



Measured memory_bytes: 16708
#include<bits/stdc++.h>
using namespace std;
const int N=20;
bool use[N];
string s[N];
string str[N];
map<string,int>mp;
int n,m,qwq;
int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)cin>>s[i];
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			str[j]+=s[i][j];
		}
	}
	for(int i=0;i<m;i++)s[i]=str[i];
	sort(s,s+m);
	do{
		random_shuffle(s,s+m);
		qwq++;
		int cnt=0;
		mp.clear();
		for(int i=0;i<n;i++)str[i]="";
		for(int i=0;i<m;i++)
		{
			for(int j=0;j<n;j++)
			{
				str[j]+=s[i][j];
			}
		}
		for(int i=0;i<n;i++)
		{
			if(mp[str[i]])
			{
				mp[str[i]]--;
				cnt--;
			}else{
				string t=str[i];
				reverse(t.begin(),t.end());
				cnt++;
				mp[t]++;
			}
		}
		if(cnt==1||cnt==0)
		{
			cout<<"YES\n";
			return 0;
		}
		if(qwq==2e5)break;
	}while(true);
	cout<<"NO\n";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define dunk(a) cout << (a) << endl
#define rall(a) (a).rbegin(),(a).rend()
const int INF = 2e9;
using namespace std;
using Graph = vector<vector<int>>;
typedef pair<int,int> P;
typedef long long ll;

int main(){
    double l; cin >> l;

    cout << fixed << setprecision(10) << (l/3.0000000000)*(l/3.0000000000)*(l/3.0000000000) << endl;
}

Measured memory_bytes: 256
N, x = gets.chomp.split(" ").map(&:to_i)
a = gets.chomp.split(" ").map(&:to_i).sort
if a.inject(&:+) < x
    puts N - 1
else 
    ans = 0
    count = 0
    a.each do |ai|
        count += ai
        if count <= x
            ans += 1
        else
            break
        end
    end
    puts ans
end

Measured memory_bytes: 1788
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <bitset>
using namespace std;
using ll = long long;
using itn = int;
const ll MOD = 1000000007;
const ll INF = MOD * MOD;
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; }

ll dp[100010];

int main() {

    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;

    for (int i = 4; i <= 30; i++) {
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
    }

    int n, res;

    while(true) {

        cin >> n;
        if (n == 0) break;

        res = 0;

        res = dp[n] / 3650;
        if (dp[n] % 3650 > 0) res++;

        cout << res << endl;
    }

    return 0;

}


Measured memory_bytes: 3048
n = int(input())
a = list(map(int, input().split()))

c = -1
b = 1
ans = 0
for i in a:
    if b == i:
        if i == 1:
            c = 1
        b += 1
    else:
        ans += 1

if c == -1:
    ans = -1

print(ans)

Measured memory_bytes: 77516
#include <cmath>
#include <iostream>
using namespace std;
int n, a[256];
int main() {
	while (cin >> n, n) {
		for (int i = 0; i < n; i++) cin >> a[i];
		int mi, mj, mk; double v = 1e+300;
		for (int i = 0; i < 16; i++) {
			for (int j = 0; j < 16; j++) {
				for (int k = 0; k < 16; k++) {
					int b[257] = { 0 }, c[257] = { 0 }; b[0] = i;
					for (int l = 1; l <= n; l++) b[l] = (j * b[l - 1] + k) % 256;
					for (int l = 0; l < n; l++) c[(a[l] + b[l + 1]) % 256]++;
					double res = 0;
					for (int l = 0; l < 256; l++) {
						if (c[l]) res -= c[l] * log(1.0 * c[l] / n);
					}
					if (v - 1e-9 > res) v = res, mi = i, mj = j, mk = k;
				}
			}
		}
		cout << mi << ' ' << mj << ' ' << mk << endl;
	}
}

Measured memory_bytes: 3320
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        char[] a = new char[n];

        for (int i = 0; i < n; i++) {
            a[i] = 'x';
        }

        int m = sc.nextInt();
        for (int i = 0; i < m; i++) {
            int s = sc.nextInt() - 1;
            char c = sc.next().charAt(0);
            if (a[s] == 'x' || a[s] == c) {
                a[s] = c;
            } else {
                System.out.println("-1");
                System.exit(0);
            }
        }

        if ((a[0] == '0' || a[0] == 'x') && n == 1) {
            a[0] = '0';
        } else if (a[0] == '0') {
            System.out.println("-1");
            System.exit(0);
        } else if (a[0] == 'x') {
            a[0] = '1';
        }
        System.out.println(String.valueOf(a).replace("x", "0"));
    }
}


Measured memory_bytes: 23892
#include <iostream>

using namespace std;

const int MAX = 100002;
 
int main(){
    int n,ans[MAX],a,b;
 
    fill(ans,ans+MAX,0);
 
    cin >> n;
    while(n--){
	cin >> a >> b;
	ans[a]++; ans[b+1]--;
    }
 
    for(int i = 1 ; i < MAX ; i++)
	ans[i] += ans[i-1];
 
    int fri = 0;
    for(int i = 1 ; i < MAX ; i++){
	if(ans[i]+1 >= i) fri = i-1; 
    }
    cout << fri << endl;
    return 0;
}

Measured memory_bytes: 3476
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,n) for(int i=(a); i<(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
void print() { cout << endl; }
template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) { cout << head; if (sizeof...(tail) != 0) cout << " "; print(forward<Tail>(tail)...); }
template <class T> void print(vector<T> &vec) { for (auto& a : vec) {	cout << a; if (&a != &vec.back()) cout << " "; } cout << endl; }
template <class T> void print(vector<vector<T>> &df) { for (auto& vec : df) {	print(vec);	} }
const int INF = 2e9;
const int MOD = 1e9+7;

// 常にxを1/2して再帰呼び出しをするので、計算量はlogNであることに注意する
// H<=10^12 なので計算量O(logN)は10^6以下となり間に合う
// ※ N/2 ではない！

ll rec(ll x) {
	if (x==1) return 1;
	else return rec(x/2)*2+1;
}

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

	ll H; cin >> H;
	cout << rec(H) << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#pragma GCC optimize ("-O3")
    using namespace std;
    #define ll long long
    #define ld long double
    #define vll vector<ll>
    #define mll map<ll,ll>
    #define pll pair<ll,ll>
    #define ff first
    #define ss second
    #define pb push_back
    #define deb(x) cout<<#x<<" : "<<x<<endl;
    #define deb2(x,y) cout<<#x<<" : "<<x<<"\t"<<#y<<" : "<<y<<endl;
    #define deb3(x,y,z) cout<<#x<<" : "<<x<<"\t"<<#y<<" : "<<y<<"\t"<<#z<<" : "<<z<<endl;
    #define deb4(w,x,y,z) cout<<#w<<" : "<<w<<"\t"<<#x<<" : "<<x<<"\t"<<#y<<" : "<<y<<"\t"<<#z<<" : "<<z<<endl;
    #define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define printv(a)  for(ll i=0;i<a.size();i++)  cout<<a[i]<<" ";
   
   
    const int mod=998244353.;
    const int N=1e6+5; 
   
    bool sortbysec(const pair<pair<ll,ll>,ll> &a, 
                      const pair<pair<ll,ll>,ll> &b) 
        { 
            return (a.second > b.second); 
        } 
        ll powermod(ll x, ll y, ll p)
        {
            ll res = 1;
            x = x % p;
            while (y > 0)
            {
                if (y & 1) res = (res*x) % p;
                y = y>>1;
                x = (x*x) % p;
            }
            return res;
        }
       
        bool isprime(int n) 
        { 
            if (n <= 1)  return false; 
            if (n <= 3)  return true; 
            if (n%2 == 0 || n%3 == 0) return false; 
            for (int i=5; i*i<=n; i=i+6) 
                if (n%i == 0 || n%(i+2) == 0) 
                   return false; 
           return true; 
        }
       
       
        int main()
    {
        FAST;
        ll n,W;
        cin>>n>>W;
        vll wt(n),val(n);
        for(ll i=0;i<n;i++)
        {
            cin>>wt[i]>>val[i];
        }
       ll K[n+1][W+1];
       for(ll i=0;i<=n;i++)
       {
           for(ll w=0;w<=W;w++)
           {
               if(i==0 || w==0)
               K[i][w]=0;
               else if(wt[i-1]<=w)
               K[i][w]=max(val[i-1]+K[i-1][w-wt[i-1]],K[i-1][w]);
               else 
               K[i][w]=K[i-1][w];
           }
       }
       cout<<K[n][W];
       
        return 0;
    }

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

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

    int N = S.size();

    int o_count = 0;
    int z_count = 0;

    for(int i = 0;i < N;i++){
        if(i % 2 == 0 && S[i] == '1'){
            o_count++;
        }
        if(i % 2 == 1 && S[i] == '0'){
            o_count++;
        }
            if(i % 2 == 0 && S[i] == '0'){
            z_count++;
        }
        if(i % 2 == 1 && S[i] == '1'){
            z_count++;
        }
     
    }
    cout << min(o_count,z_count) << endl;
}

Measured memory_bytes: 512
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder
{

    static class Program
    {
        static void Main()
        {
            Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });

            long X;long A;long B;
            Multi(out X, out A, out B);
            string ans = A >= B ? "delicious" : B - A <= X ? "safe" : "dangerous";

            Console.WriteLine(ans);


            Console.Out.Flush();
            Console.ReadKey();
        }


        static public string GetStr() { return Console.ReadLine().Trim(); }
        static public char GetChar() { return Console.ReadLine().Trim()[0]; }
        static public int GetInt() { return int.Parse(Console.ReadLine()); }
        static public long GetLong() { return long.Parse(Console.ReadLine()); }
        static public string[] GetStrArray() { return Console.ReadLine().Split(' '); }
        static public int[] GetIntArray() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
        static public long[] GetLongArray() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
        static public char[] GetCharArray() { return Console.ReadLine().Split(' ').Select(char.Parse).ToArray(); }
        static public Double[] GetDoubleArray() { return Console.ReadLine().Split(' ').Select(double.Parse).ToArray(); }
        static public void WriteObjects<T>(IEnumerable<T> values) { foreach (var o in values) { Console.Write(o + " "); } }
        static string yesno(this bool b) { return b ? "yes" : "no"; }
        static string YesNo(this bool b) { return b ? "Yes" : "No"; }
        static string YESNO(this bool b) { return b ? "YES" : "NO"; }

        static bool eq<T, U>() => typeof(T).Equals(typeof(U));
        static T ct<T, U>(U a) => (T)Convert.ChangeType(a, typeof(T));
        static T cv<T>(string s) => eq<T, int>() ? ct<T, int>(int.Parse(s))
                           : eq<T, long>() ? ct<T, long>(long.Parse(s))
                           : eq<T, double>() ? ct<T, double>(double.Parse(s))
                           : eq<T, char>() ? ct<T, char>(s[0])
                                             : ct<T, string>(s);
        static void Multi<T>(out T a) => a = cv<T>(GetStr());
        static void Multi<T, U>(out T a, out U b)
        {
            var ar = GetStrArray(); a = cv<T>(ar[0]); b = cv<U>(ar[1]);
        }
        static void Multi<T, U, V>(out T a, out U b, out V c)
        {
            var ar = GetStrArray(); a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]);
        }
        static void Multi<T, U, V,W>(out T a, out U b, out V c, out W d)
        {
            var ar = GetStrArray(); a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]); d = cv<W>(ar[3]);
        }
        static void Multi<T, U, V, W,X>(out T a, out U b, out V c, out W d,out X e)
        {
            var ar = GetStrArray(); a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]); d = cv<W>(ar[3]);e = cv<X>(ar[4]);
        }
    }
}

Measured memory_bytes: 11220
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var Arr=(input.trim()).split("\n");
while(true){
   if(Arr.length==0)break;
   var nr=Arr.shift().split(" ").map(Number);
   var n=nr[0];
   var r=nr[1];
   var card=[];
   for(var i=0;i<n;i++)card[i]=i;
   var arr=Arr.shift().split(" ").map(Number);
   for(var i=0;i<r;i++){
      var v=arr[i];
      var a=[];
      var b=[];
      for(var j=0;j<n;j++)(Math.floor(n/2)>j)?b.push(card[j]): a.push(card[j]);
      card=[];
      while(true){
         if(a.length==0 && b.length==0)break;
         card=card.concat(a.splice(0,v));
         card=card.concat(b.splice(0,v));
      }
   }
   console.log(card[card.length-1]);
}

Measured memory_bytes: 10444