akhauriyash/Code-Regression huggingface dataset:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author anand.oza
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        AGrouping2 solver = new AGrouping2();
        solver.solve(1, in, out);
        out.close();
    }

    static class AGrouping2 {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();

            out.println(n / 3);
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}



Measured memory_bytes: 22484
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
int main() {
	int n;	cin >> n;
  	string s;	cin >> s;
  	
  	int cnt = 0;
  	char tmp = s.at(0);
  	for(int i = 1; i < n; i++){
    	if(tmp == s.at(i)) cnt += 1;
      	tmp = s.at(i);
    }
  	
  	cout << n - cnt << endl;
}


Measured memory_bytes: 512
//#######################     Starting_with_name_of_ALLAH     ##############################
//#######################     Bismillahir_rahmair_raheem      ##############################
 
//                      coded in 2020
//
//                   Shamim Ahammad Rasel
//                  Begum Rokeya University
//                 shamim.brur.cse@gmail.com
//                    I love your thinking 


#include<bits/stdc++.h>
#define tc()         int tc;cin>>tc;while(tc--)

using namespace std;

void shomoy();

int main(){
    long long i,j,k,x,y,a,b,n,total,count,sum,temp,len;

    int c,d;
    long long int mul;
    cin>>a>>b>>c>>d;
    long long arr[4];
    arr[0] = a*c;
    arr[1] = a*d;
    arr[2] = b*c;
    arr[3] = b*d;
    sort(arr,arr+4);
    cout<<arr[3]<<endl;





shomoy();

return 0;
}






















void shomoy(){
    #ifndef ONLINE_JUDGE
        cerr<<"---------END OF OUTPUT---------------\n";
        cerr<<"---------Time  :"<<1.0*clock()/CLOCKS_PER_SEC<<"s------------\n";
        
    #endif
 
}


Measured memory_bytes: 3636
from collections import deque

# 上下左右1マスを検索するために必要とする
dis_x = [1, 0, -1, 0]
dis_y = [0, 1, 0, -1]

# 迷路の縦幅,横幅
max_h, max_w = map(int, input().split())

wall_count = 0
s = []
for _ in range(max_h):
    line = input()
    wall_count += line.count("#")
    # 横1マスを壁でPadding. これでindex out of boundを防ぐ
    s.append(list("#{}#".format(line)))

# 縦1マスを壁でPadding. これでindex out of boundを防ぐ
s = [list("#" * (max_w + 2))] + s + [list("#" * (max_w + 2))]

# 迷路と同じサイズの距離表を作成.
# 値が0 -> 未訪問, それ以外 -> スタート地点からそれまでの距離となる
dist = [ [0] * (max_w + 2) for _ in range(max_h+2)]

que = deque([(1, 1)])

while que:
  h, w = que.popleft()

  for i in range(4):
    dx, dy = dis_x[i], dis_y[i]
    if s[h+dy][w+dx] == '.' and dist[h+dy][w+dx] == 0:
      dist[h+dy][w+dx] = dist[h][w] + 1
      que.append((h+dy, w+dx))

result = max_h*max_w - wall_count - dist[max_h][max_w] - 1
if dist[max_h][max_w] == 0:
  print(-1)
else:
  print(result)

Measured memory_bytes: 3316
macro_rules! get {
    ($t:ty) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
            get!($t)
        ).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
            get!($($t),*)
        ).collect::<Vec<_>>()
    };
}

fn main() {
    let (_n, tt) = get!(usize, i64);
    let ts = get!(String).split_whitespace().map(|t| t.parse::<i64>().unwrap()).collect::<Vec<_>>();
    let mut l = 0;
    let mut r = tt;
    let mut s = 0;
    for &t in ts[1..].into_iter() {
        if r >= t {
            r = t + tt;
        } else {
            s += r - l;
            l = t;
            r = t + tt;
        }
    }
    println!("{}", s + r - l);
}

Measured memory_bytes: 8444
#include "bits/stdc++.h"
using namespace std;
#define CK(N, A, B) (A <= N && N < B)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define RREP(i, a, b) for (int i = (b - 1); a <= i; i--)
#define F first
#define S second
typedef long long ll;

const int INF = 1e9 + 7;
const long long LLINF = 1e18;

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

    ll ans=b/x;
    if(a==0) ans++;
    else ans-=(a-1)/x;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
import java.lang.reflect.Array;
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		// 入力
		int N = sc.nextInt();                
		int K = sc.nextInt();
		int x[] = new int[N];
		for (int i = 0; i < N; i++) {
			x[i] = sc.nextInt();
		}
		int result = 0;
		for (int i = 0; i < N-K+1; i++) {
			int distance = Math.abs(x[i]) + Math.abs(x[i] - x[i+K-1]);
			if (result == 0 || result > distance) {
				result = distance;
			}
			distance = Math.abs(x[i+K-1]) + Math.abs(x[i+K-1] - x[i]);
			if (result == 0 || result > distance) {
				result = distance;
			}
		}
		System.out.println(result);			
	}	
}


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

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

using namespace std;

int main() {
    char b; cin >> b;

    char ans;

    if(b == 'A') {
        ans = 'T';
    } else if(b == 'T') {
        ans = 'A';
    } else if(b == 'C') {
        ans = 'G';
    } else {
        ans = 'C';
    }

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



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lim 100005
#define pb push_back
#define S second
#define pb push_back
#define mp make_pair
#define INF 1e16
#define fr(i,j,k) for(ll i=j;i<=k;i++)
#define frd(i,j,k) for(ll i=j;i>=k;i--)
#define F first
#define sd(n) scanf("%lld",&n)
#define pd(n) printf("%lld\n",n)
#define db double
#define mod 1000000007
#define pii pair<ll,ll>
ll getans(ll i,ll j)
{
    ll rem=i%j;
    rem=j-rem;
    rem%=j;
    return rem;

}
int main()
{
    ll n;
    cin>>n;
    ll a[n],b[n];
    //cout<<n<<endl;
    for(ll i=0;i<n;i++)
        {   //cout<<i<<endl;
            cin>>a[i]>>b[i];
        }
    ll ans=0;
    for(ll i=n-1;i>=0;i--)
    {
        a[i]+=ans;
        ans+=getans(a[i],b[i]);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 1792
#include<stdio.h>

int main(){
    int n, max = 0, min = 0, i;
    
    scanf("%d", &n);
    
    int R[n];
    
    for(i = 0; i < n; i++){
    	scanf("%d", &R[i]);
    }
    
    min = R[0];
    max = R[1] - R[0];
    for(i = 1; i <= n - 1; i++){
    	if(R[i] - min > max){
    		max = R[i] - min;
    	}
    	if(R[i] < min){
    		min = R[i];
    	}
    	//printf("%d\n", R[i]);
    }
    
   	printf("%d\n", max);
   
    return 0;
}





Measured memory_bytes: 2516
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstdlib>
#include<queue>
#include<set>
#include<cstdio>

using namespace std;

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

typedef vector<int> vec;
typedef vector<vec> mat;

const ll mod = 1000000007;

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    rep(i, n) a[i]--;
    vector<int> idx(n);
    rep(i, n) idx[a[i]] = i;
    ll ans = 0;
    set<int> s;
    for (int x = n - 1; x >= 0; x--){
        int i = idx[x];
        ll c = 0;
        {
            s.insert(i);
            vector<int> l(2,-1);
            vector<int> r(2, n);
            {
                auto it = s.find(i);
                rep(j, 2){
                    if(it == s.begin()) break;
                    it--;
                    l[j] = *it;
                }
            }
            {
                auto it = s.find(i);
                rep(j, 2){
                    it++;
                    if(it == s.end()) break;
                    r[j] = *it;
                }
            }
            vector<int> ls(2);
            ls[0] = i - l[0]; ls[1] = l[0] - l[1]; 
            vector<int> rs(2);
            rs[0] = r[0]-i; rs[1] = r[1] - r[0]; 
            c = (ll)ls[0]*rs[1] + (ll)ls[1]*rs[0];
        }
        ans += c * (x + 1);
    }
    cout << ans << endl;
}

Measured memory_bytes: 8684
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n,now,ans,in;
    ans=0;
    cin >> n;
    vector<int> bot(n);
    for(int i=0;i<n;i++){
      cin>>in;
      bot[i]=in-1;
    }
    for(;;){
      if(now==1){
        break;
      }
      if(ans>n){
        ans=-1;
        break;
      }
      ans++;
      now=bot[now];
    }
  cout<<ans<<endl;
}


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

vector<int> ans;
int pre[40];
int in[40];
int N;

struct Node {
	int left;
	int right;
};

void solve(int begin, int end, int& j) {
	int mid;
	for (int i = begin; i < end; i++) {
		if (in[i] == pre[j]) {
			mid = i;
		}
	}

	if(begin != mid)solve(begin, mid, ++j);
	if(mid + 1 != end)solve(mid + 1, end, ++j);
	ans.push_back(in[mid]);
}

int main() {

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> pre[i];
	}
	for (int i = 0; i < N; i++) {
		cin >> in[i];
	}

	int j = 0;
	solve(0, N, j);
	
	for (int i = 0; i < N; i++) {
		cout << ans[i];
		if (i < N - 1)cout << " ";
	}
	cout << endl;
	
	return 0;
}

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

using namespace std;

static vector<int> VList;
static vector<int> CList;

int main()
{
  // 入力受け取り
  int N;
  cin >> N;
  VList.resize(N);
  CList.resize(N);
  
  int ans=0;
  for (int i=0; i<N; i++) cin >> VList.at(i);
  for (int i=0; i<N; i++) cin >> CList.at(i);
  for (int i=0; i<N; i++) {
    if(VList[i] > CList[i]) {
      ans+=(VList[i]-CList[i]);
    }
  }
  
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int N;
int s[100];

int main()
{
        cin >> N;
        for (int i=0; i<N; i++)
                cin >> s[i];

        int mx=101,sm=0;
        for (int i=0; i<N; i++) {
                sm += s[i];
                if (s[i]%10 != 0 && s[i] < mx)
                        mx = s[i];
        }

        if (mx == 101)
                cout << "0\n";
        else if (sm%10 == 0)
                cout << sm-mx << "\n";
        else
                cout << sm << "\n";
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define USE_LLONG_AS_INT
#ifdef USE_LLONG_AS_INT
#define int long long
#define inf (1ll<<60)
#else
#define inf (1<<30)
#endif
#define rep(i,n) for(int i=0;i<(n);i++)
#define Rep(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a,b) for(int i=(a);i<=(b);i++)
#define rev(i,n) for(int i=(n)-1;i>=0;i--)
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define eb emplace_back
#define pi pair<int,int>
#define vp vector<pair<int,int>>
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MEMSET(a) memset(a,0,sizeof(a))
#define Yes(f) cout<<(f?"Yes":"No")<<endl
#define yes(f) cout<<(f?"yes":"no")<<endl
#define YES(f) cout<<(f?"YES":"NO")<<endl
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v), greater<int>())

using namespace std;

const int mod=1e9+7;
const string sp=" ";

void run();

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(12);
}

signed main(){
    init();
    run();
    return 0;
}

int n;
vector<vp> g;

void solve(){
    vi d(n,inf);
    priority_queue<pi,vp,greater<pi>> q;
    d[0]=0;
    q.push({0,0});
    while(!q.empty()){
        pi p=q.top();
        q.pop();
        int v=p.se;
        if(d[v]<p.fi)continue;
        for(pi e:g[v]){
            if(d[e.se]>d[v]+e.fi){
                d[e.se]=d[v]+e.fi;
                q.push({d[e.se],e.se});
            }
        }
    }
    rep(i,n){
        cout<<i<<sp<<d[i]<<endl;
    }
}

void run(){
    cin>>n;
    g.resize(n);
    rep(i,n){
        int u,k;
        cin>>u>>k;
        rep(j,k){
            int v,c;
            cin>>v>>c;
            g[u].eb(pi(c,v));
        }
    }
    solve();
}


Measured memory_bytes: 12060
inputted = input().split(" ")
N=int(inputted[0])
K=int(inputted[1])
s = [i for i in input() if i != ' ']

num=0
while True:
  num+=1
  match=[i for i in str(num) if i in s]
  if num>=N and len(match)==0:
    print(num)
    break

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define _GLIBCXX_DEBUG
#define V vector<ll>
using namespace std;
using ll = long long;


int main(){
   int n,T;
   cin >> n >> T;
   vector<int> c(n),t(n);
   rep(i, 0, n){
      cin >> c[i] >> t[i] ;
   }
   int ans = 1001;
   rep(i,0,n){
      if(t[i] <= T){
         ans = min(ans, c[i]);
      }
   }
   if(ans == 1001) cout << "TLE" << endl;
   else cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/




int N, W, w[101], v[101];
ll dp[101][201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> W;
    rep(i, 0, N) cin >> w[i] >> v[i];

    rep(i, 0, N) rep(tot, 0, W) {
        chmax(dp[i + 1][tot], dp[i][tot]);
        chmax(dp[i + 1][tot + w[i]], dp[i][tot] + v[i]);
    }

    ll ans = 0;
    rep(tot, 0, W + 1) chmax(ans, dp[N][tot]);
    cout << ans << endl;
}



Measured memory_bytes: 156544
from itertools import combinations

N, M, X = map(int, input().split())
skill = [0] * M
N_list = []
C_sum = 0
all_list = [0] * (M+1)

res_list = 0
for i in range(N):
  list_ = list(map(int, input().split()))
  N_list.append(list_)
  all_list = [all_list[i]+list_[i] for i in range(M+1)]

result = []  
for i in range(1, N+1):
  ref = list(combinations(N_list, i))
  for j in range(len(ref)):
    sums = [0] * (M+1)
    for k in range(i):
      sums = [sums[l]+ref[j][k][l] for l in range(M+1)]
    result.append(sums)
kekka = []
for i in range(len(result)):
  if all(result[i][j]>=X for j in range(1, M+1)):
    kekka.append(result[i][0])
if kekka != []:
  print(min(kekka))
else:
  print(-1)

Measured memory_bytes: 11844
# _*_ coding:utf-8 _*_
#  Atcoder_Beginners_Contest114-A
#  https://beta.atcoder.jp/contests/abc114/tasks/abc114_a


def check_753(s):

	if(s == '7' or s=='5' or s=='3'):
		answer = "YES"
	else:
		answer = "NO"
	return answer


if __name__ == '__main__':
	problemStr=input()
	answerStr=check_753(problemStr)
	print(answerStr)

Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i ,n) for(int i = 0 ; i < (n) ; i ++ )
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
using ll = long long;
using vll=vector<ll>;
using P = pair<int, int>;
const int inf=1e9+7;
const ll INF=1e18;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

int main() {
 string s;
  cin>>s;
  int n=s.size();
 ///
  rep(i,n){
   if(s[i]=='?') s[i]='D'; 
  }
  cout<<s<<endl;
}

Measured memory_bytes: 3712
#include <iostream>
#include <math.h>
#include <queue>
#include <algorithm>
#include <map>
#include <set>
#include <cstdlib>
#include <unordered_map>
#include <numeric>
#include <functional>
#include <limits.h>
#include <utility>

using namespace std;

#define fs first
#define sc second

typedef long long ll;
typedef pair<ll, ll> P;

const ll mod = 1000000007;
ll fact[420000];
ll invfact[420000];


inline ll take_mod(ll a){
    return (a % mod + mod) % mod;
}

inline ll add(ll a, ll b){
    return take_mod(a+b);
}

inline ll sub(ll a, ll b){
    return take_mod(a+mod-b);
}


inline ll mul(ll a, ll b){
    return take_mod(a * b);
}

inline ll pow(ll x, ll n){
    ll res = 1LL;
    while(n > 0){
        if(n & 1) res = mul(res, x);
        x = mul(x, x);
        n >>= 1;
    }
    return res;
}

ll mod_inv(ll x){
    return pow(x, mod-2);
}

// nは上限
void make_fact(ll n){
    fact[0] = 1;
    ll res = 1;
    for(int i = 1; i <= n; i++){
        fact[i] = res;
        res = mul(res, i+1);
    }
}

// nは上限
void make_invfact(ll n){
    invfact[0] = 1;
    invfact[n] = mod_inv(fact[n]);
    for(int i = n-1; i >= 1; i--){
        invfact[i] = mul(invfact[i + 1], i + 1);
    }
}

ll perm(ll n, ll k){
    return mul(fact[n], invfact[n-k]);
}

ll comb(ll n, ll k){
    return mul(mul(fact[n], invfact[n-k]), invfact[k]);
}


int main(){
    ll H, W, N, r[3100], c[3100];
    make_fact(410000);
    make_invfact(410000);

    vector<P> v;
    cin >> H >> W >> N;

    for(int i = 0; i < N; i++){
        cin >> r[i] >> c[i];
        v.emplace_back(P(r[i]+c[i], c[i]));
    }
    v.emplace_back(P(2, 1));
    v.emplace_back(P(H+W, W));

    sort(v.begin(), v.end());
    for(int i = 0; i <= N+1; i++){
        r[i] = v[i].fs - v[i].sc;
        c[i] = v[i].sc;
    }

    ll dp[3010][2];
    for(int i = 0; i < 3010; i++){
        for(int j = 0; j < 2; j++){
            dp[i][j] = 0;
        }
    }
    dp[0][0] = 0;
    dp[0][1] = 1;
    for(int i = 1; i < N+2; i++){
        for(int j = 0; j < i; j++){
            if(r[i] >= r[j] && c[i] >= c[j]){
                dp[i][0] = add(dp[i][0], mul(comb(r[i]-r[j]+c[i]-c[j], r[i]-r[j]), dp[j][1]));
                dp[i][1] = add(dp[i][1], mul(comb(r[i]-r[j]+c[i]-c[j], r[i]-r[j]), dp[j][0]));
            }
        }
    }

    cout << sub(dp[N+1][0], dp[N+1][1])  << endl;

    return 0;
}

Measured memory_bytes: 6912
#include <iostream>
using namespace std;
int main() {
  unsigned long long n,a,b,loop=0,rem=0;
  cin>>n>>a>>b;
  loop=n/(a+b);
  rem=n%(a+b);
  if(rem>a)
    rem=a;
  cout<<loop*a+rem<<endl;
}

Measured memory_bytes: 256
# abc130_b.py
# https://atcoder.jp/contests/abc130/tasks/abc130_b

# B - Bounding /
# 実行時間制限: 2 sec / メモリ制限: 1024 MB
# 配点 : 200点

# 問題文
# 数直線上を N+1回跳ねるボールがあり、1 回目は 座標 D1=0, i 回目は 座標 Di=Di−1+Li−1(2≤i≤N+1)で跳ねます。
# 数直線の座標が X以下の領域でボールが跳ねる回数は何回でしょうか。

# 制約
#     1≤N≤100
#     1≤Li≤100
#     1≤X≤10000
#     入力は全て整数である

# 入力
# 入力は以下の形式で標準入力から与えられる。
# N X
# L1 L2 ... LN−1 LN

# 出力
# 数直線の座標が X以下の領域でボールが跳ねる回数を出力せよ。

# 入力例 1
# 3 6
# 3 4 5

# 出力例 1
# 2

# ボールは順に座標 0,3,7,12で跳ねるので、座標 6 以下の領域で跳ねる回数は 2回です。

# 入力例 2
# 4 9
# 3 3 3 3

# 出力例 2
# 4

# ボールは順に座標 0,3,6,9,12で跳ねるので、座標 9 以下の領域で跳ねる回数は 4 回です。


global FLAG_LOG
FLAG_LOG = False


def log(value):
    # FLAG_LOG = True
    # FLAG_LOG = False
    if FLAG_LOG:
        print(str(value))


def calculation(lines):
    # S = lines[0]
    # N = int(lines[0])
    N, X = list(map(int, lines[0].split()))
    values = list(map(int, lines[1].split()))
    # values = list(map(int, lines[2].split()))
    # values = list()
    # for i in range(6):
    #     values.append(int(lines[i]))
    # valueses = list()
    # for i in range(M):
    #     valueses.append(list(map(int, lines[i+1].split())))

    su = 0
    cnt = 1
    for i in range(N):
        su += values[i]
        if su <= X: 
            cnt += 1
        else:
            break

    return [cnt]


# 引数を取得
def get_input_lines(lines_count):
    lines = list()
    for _ in range(lines_count):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['3 6', '3 4 5']
        lines_export = [2]
    if pattern == 2:
        lines_input = ['4 9', '3 3 3 3']
        lines_export = [4]
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    global FLAG_LOG
    if len(args) == 1:
        mode = 0
        FLAG_LOG = False
    else:
        mode = int(args[1])
        FLAG_LOG = True
    return mode


# 主処理
def main():
    import time
    started = time.time()
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines(2)
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = calculation(lines_input)

    for line_result in lines_result:
        print(line_result)

    # if mode > 0:
    #     print(f'lines_input=[{lines_input}]')
    #     print(f'lines_export=[{lines_export}]')
    #     print(f'lines_result=[{lines_result}]')
    #     if lines_result == lines_export:
    #         print('OK')
    #     else:
    #         print('NG')
    # finished = time.time()
    # duration = finished - started
    # print(f'duration=[{duration}]')


# 起動処理
if __name__ == '__main__':
    main()


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

using namespace std;

bool good(const char ch){

    return ch=='A' or ch=='T' or ch=='C' or ch=='G';
}

int main(){

    string s;
    cin>>s;

    int lg=0,best=0;

    for(auto &it:s){

        if(good(it))
            ++lg;
        else{

            best=max(best,lg);
            lg=0;
        }
    }

    cout<<max(best,lg);

    return 0;
}


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=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define dunk(a) cout << (a) << "\n"
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int inf = 1001001001;
const int mod = 1000000007;

vector<int> to[100005];
int n;

vector<int> dist;
void dfs(int v, int d = 0, int p = -1) {
	dist[v] = d;
	for (auto& c : to[v]) {
		if (c == p) continue;
		dfs(c, d + 1, v);
	}
	return;
}

vector<int> calcDist(int s) {
	dist = vector<int>(n);
	dfs(s);
	return dist;
}

int main() {
	cin >> n;
	int s, t;
	cin >> s >> t;
	s--; t--;
	rep(i, n - 1) {
		int a, b; cin >> a >> b;
		a--; b--;
		to[a].emplace_back(b);
		to[b].emplace_back(a);
	}

	vector<int> distS = calcDist(s);
	vector<int> distT = calcDist(t);

	int mx = 0;
	rep(i, n) {
		if (distS[i] < distT[i]) {
			mx = max(mx, distT[i]);
		}
	}
	int ans = mx - 1;
	dunk(ans);
	return 0;
 }


Measured memory_bytes: 10744
/* AtCoder コピペ */
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repEq(i, n) for (int i = 0; i <= (int)(n); i++)
#define repVector(i, v) for (auto i = v.begin(); i != v.end(); ++i)

#define ifBetween(n, a, b) if (n > a && n < b)
#define ifBetweenEq(n, a, b) if (n >= a && n <= b)

int main() {
  	int N;
	cin >> N;
  
  	int l[N];
  	rep(i, N) {
  		cin >> l[i];
   	}
  
  	vector<int> vec(l, l + sizeof l / sizeof l[0]);
  	sort(vec.begin(), vec.end());

  	int total = 0;

  	for (auto i = vec.begin(); i != vec.end(); ++i) {
    	for (auto j = i + 1; j != vec.end(); ++j) {
          	if(!(*(j + 1) < *i + *j)) continue;

        	for (auto k = j + 1; k != vec.end(); ++k) {
            	bool b1 = *i < *j + *k;
              	bool b2 = *j < *k + *i;
              	bool b3 = *k < *i + *j;
              
              	if (b1 && b2 && b3) total++;
              	else break;
            }
        }
    }
  
  	cout << total << endl;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define repk(i,k,n) for (ll i = k; i < (ll)(n); ++i)
#define MAX 500000001000000000
#define MOD 1000000007
typedef long long  ll;

using namespace std;



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

	string N;
	cin >> N;
	int K;
	cin >> K;

	int n = N.size(); // Nの桁数

	ll dp[110][2][5] = {};  // dp[i][j][k] =:条件を満たす数字の個数,(i:上からのi桁目まで, j:N未満確定であるかのフラグ, k:0でない数の総数)

	dp[0][0][0] = 1; // 初期化
	rep(i, n) {  
		rep(j, 2) {  
			rep(k, 4) { // 制約より(k <= 3)のみループすればいい
				int lim = j ? 9 : N[i] - '0'; // i+1桁目に配置することのできる数の最大値
				rep(d, lim + 1) { // 配置できる数までループ
					dp[i + 1][j || d < lim][k + (d > 0)] += dp[i][j][k]; // dが0でないなら(0以上なら)kに1足す
				}
			}
		}
	}

	cout << dp[n][0][K] + dp[n][1][K] << '\n'; // 未満確定じゃないのを足すのを忘れないように！
	return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
	static Scanner sc = new Scanner(System.in);
	static ArrayList<String> list = new ArrayList<String>();
	static int caseNumber, n;
	public static void main(String[] args) {
		while(read()){

		}
	}
	static boolean read(){
		if(!sc.hasNext())return false;
		n = sc.nextInt();
		for(int i = 0; i < n; i++){
			int j = sc.nextInt();
			caseNumber++;
			list.add(Integer.toString(j));
			solve();
		}
		return true;
	}
	static void solve(){
		calc();
		System.out.println("Case "+caseNumber+":");
		print();
		list.removeAll(list);
	}
	static void calc(){
		for(int k = 0; k < 11; k++){
			int x = Integer.parseInt(list.get(k));
			String s = Integer.toString(x*x);
			for(int i = s.length(); i < 8; i++){
				s = "0" + s;
			}
			String newS = "";
			for(int i = 2; i <= 5; i++){
				newS = newS + s.charAt(i);
			}
			list.add(newS);
		}
	}
	static void print(){
		for(int i = 1; i < 11; i++){
			int x = Integer.parseInt(list.get(i));
			System.out.println(x);
		}
	}
}

Measured memory_bytes: 12000
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using static System.Console;
using static System.Int32;
using static System.Math;
 
class Program
{
    static void Main(string[] args)
    {
        label:
        WriteLine(hoge() ? "Yes" : "No");
    }

    static bool hoge()
    {
        var org = Parse(ReadLine());
        int f = 0;
        for (int n = org; 0 < n; n /= 10)
        {
            f += n % 10;
        }
        return org % f == 0;
    }
}


Measured memory_bytes: 13140
#include <iostream>

using namespace std;

int main() {
  int N;
  cin >> N;
  int P [N];

  for(int i = 0; i < N; i++) {
    cin >> P[i];
  }

  int count = 0;
  int min = P[0];
  for(int i = 0; i < N; i++) {
    int p = P[i];
    if(p <= min) {
      count++;
      min = p;
    }
  }

  cout << count;

  return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int N, M, c, sum = 0;
    int *A;
    scanf("%d %d", &N, &M);
    A = (int *)malloc(sizeof(int) * M);
    for (c = 0; c < M; ++c)
    {
        scanf("%d", A + c);
        sum += A[c];
    }
    if (sum > N)
    {
        printf("-1");
    }
    else
    {
        printf("%d", N - sum);
    }
    free(A);
    return 0;
}

Measured memory_bytes: 1728
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <tuple>

using namespace std;
typedef long long ll;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
const int INF = 1<<29;

int main(){
    ll N;
    cin >> N;
    cout << N*(N-1)/2 << endl;
    return 0;
}


Measured memory_bytes: 256
#include <ext/pb_ds/assoc_container.hpp>
#include <bits/stdc++.h>
using namespace std;
using namespace __gnu_pbds;
template <class c, class cmp = less<c> > using ordered_set = tree<c, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...) 
#endif
template<class T> ostream& operator<<(ostream &os, vector<T> V) {os << "[ "; for(auto v : V) os << v << " "; return os << "]";}
template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P) {return os << "(" << P.first << "," << P.second << ")";}
template <typename T,typename U>pair<T,U> operator+(const pair<T,U> & l,const std::pair<T,U> & r) { return {l.first+r.first,l.second+r.second};}
typedef long long int ll;
const ll mod =998244353;
const int maxn = 300005;
#define endl '\n'
#define ld long double
#define int ll
#define all(x) (x).begin(),(x).end()
int32_t main()
{ 
  IOS


  int d, t, s;
  cin >> d >> t >> s;
  if(t*s>=d){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
  

  










  
    
} 



Measured memory_bytes: 3664
import functools

import os

INF = float('inf')


def inp():
    return int(input())


def inpf():
    return float(input())


def inps():
    return input()


def inl():
    return list(map(int, input().split()))


def inlf():
    return list(map(float, input().split()))


def inls():
    return input().split()


def debug(fn):
    if not os.getenv('LOCAL'):
        return fn

    @functools.wraps(fn)
    def wrapper(*args, **kwargs):
        print('DEBUG: {}({}) -> '.format(
            fn.__name__,
            ', '.join(
                list(map(str, args)) +
                ['{}={}'.format(k, str(v)) for k, v in kwargs.items()]
            )
        ), end='')
        ret = fn(*args, **kwargs)
        print(ret)
        return ret

    return wrapper


a, b = inl()
print('Yay!' if a*2 <= 16 and b*2 <= 16 else ':(')


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

int main() {
 	char grid1, grid2, grid3;
  	//いくつ1があるかをカウントする
    int cnt = 0;
  	
  	//各入力取得
  	cin >> grid1 >> grid2 >> grid3;
 	
 	if(grid1 == '1')
    {
    	cnt++;
    }
  	
  	if(grid2 == '1')
    {
    	cnt++;
    }
  
  	if(grid3 == '1')
    {
    	cnt++;
    }
  
  cout << cnt << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>  // ver1.9.4
#define int long long
#define ALL(v) (v).begin(),(v).end()
#define Vi vector<int>
#define pb push_back
#define mp make_pair
#define cYES cout<<"YES"<<endl
#define cNO cout<<"NO"<<endl
#define cYes cout<<"Yes"<<endl
#define cNo cout<<"No"<<endl
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repeq(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(int i=a;i>b;i--)
#define repreq(i,a,b) for(int i=a;i>=b;i--)
#define leng(n) (int)(log10(n)+1)
#define Vout(a) rep(i,0,a.size()-1)cout<<a[i]<<' ';cout<<a[a.size()-1]<<endl;
#define INF 9000000000000000000  //  9.0 * 10^18
#define MOD 1000000007  //  10^9 + 7
using namespace std;

signed main() {
  cout << fixed << setprecision(15);
  int n;
  cin >> n;
  int odd=1,memo;
  rep(i,0,n){
    cin >> memo;
    if(memo%2==0) odd*=2;
  }
  memo = pow(3,n);
  cout << memo - odd << endl;
  return 0;
}


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

int main() {
  int N, m = 0, a = 0, b = 0, c = 0, d = 0;
  
  cin >> N;
  string x;

  for(int i = 0; i < N; i++){
    string s;
    cin >> s;
    if(s == "P" && a == 0){
      a++, m++;
    }
    if(s == "W" && b == 0){
      b++, m++;
    }
    if(s == "G" && c == 0){
      c++, m++;
    }
    if(s == "Y" && d == 0){
      d++, m++;
    }
  }
  if(m == 3){
    cout << "Three";
  }
  if(m == 4){
    cout << "Four";
  }
}
      


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);
#define ee endl
#define lli long long int
#define li long int
#define vi vector <int>
#define vp vector <pair<int,int>>
#define pb push_back
#define pob pop_back
#define mp make_pair
#define fr(i,s,n) for(int i=s;i<n;i++)
using namespace std;
///author by sahil_dabhi

int my_own()
{
lli i,count=0;
string s,t;
cin>>s>>t;
fr(i,0,s.size())
    {if(s[i]!=t[i])
        count++;}
cout<<count;
return 0;
}

int main()
{
    IOS
    int t=1;
   // cin>>t;  ///for test-case
    while(t--)
    my_own();
    return 0;
}


Measured memory_bytes: 3832
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    int n;
    cin >> n;
    vector<int> x(n), y(n), w(n);
    map<pair<int, int>, int> s;
    for (int i = 0; i < n; ++i) {
        scanf("%d %d %d", &x[i], &y[i], &w[i]);
        s[{x[i], y[i]}] += w[i];
    }
    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = -1; j < 1; ++j) {
            for (int k = -1; k < 1; ++k) {
                ll q = 0;
                for (int l = 0; l < 2; ++l) {
                    for (int m = 0; m < 2; ++m) {
                        q += s[{x[i]+j+l, y[i]+k+m}];
                    }
                }
                ans = max(ans, q);
            }
        }
    }
    printf("%lld / 1\n", ans);
    return 0;
}


Measured memory_bytes: 60412
//------------------------------------------
// C++ templete 
//------------------------------------------
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
using ll = long long;

#define endl "\n"

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

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

//container util
//------------------------------------------
#define pb push_back
#define paired make_pair
#define ALL(a) (a).begin(),(a).end()
#define PRINT(V) for (auto v : (V)) cout << v << " "
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())

//constant
//------------------------------------------
const int MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

//math
//------------------------------------------
int QP(int a,int b){int ans=1;do{if(b&1)ans=1ll*ans*a%MOD;a=1ll*a*a%MOD;}while(b>>=1);return ans;}
int QP(int a,int b,int MOD){int ans=1;do{if(b&1)ans=1ll*ans*a%MOD;a=1ll*a*a%MOD;}while(b>>=1);return ans;}
int GCD(int a,int b){return b?GCD(b,a%b):a;}

//debug
//------------------------------------------
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//動的計画法で役に立つ関数
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 gcd(ll a, ll b) {
    if(b==0)return a;
    return gcd(b, a%b);
}

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

vector<vector<long long> > comb(int n) {
  vector<vector<long long> > v(n + 1,vector<long long>(n + 1, 0));
  for (int i = 0; i < v.size(); i++) {
    v[i][0] = 1;
    v[i][i] = 1;
  }
  for (int j = 1; j < v.size(); j++) {
    for (int k = 1; k < j; k++) {
      v[j][k] = (v[j - 1][k - 1] + v[j - 1][k]);
    }
  }
  return v;
}

VI C(600), S(600), F(600);

int move(int i, int t)
{
    if (t <= S[i]) return S[i] + C[i];
    else
    {
        while(t%F[i] != 0)
        {
            t++;
        }
        return t + C[i];
    }
}

int main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
  
    int N; cin >> N;
    REP(i, N-1)
    {
        cin >> C[i] >> S[i] >> F[i];
    }
    REP(i, N)
    {
        int t=0;
        FOR(j, i, N-1)
        {
            t = move(j, t);
        }
        cout << t << endl;
    }
    return 0;
}



Measured memory_bytes: 256
n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = list(input())
score = {"r":p, "s":r, "p":s}
ans = 0
for i in range(n):
    if i<k:
        ans += score[t[i]]
    else :
        if t[i] != t[i-k] :
            ans += score[t[i]]
        else :
            t[i]="x"
print(ans)


Measured memory_bytes: 4084
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
typedef long long ll;
const int N=200005;
int n,p1[N],p2[N];
ll a[N],sum[N];
using namespace std;

ll calc(ll a,ll b,ll c,ll d)
{
	ll x=a,y=a;
	if (x>b) x=b;
	if (x>c) x=c;
	if (x>d) x=d;
	if (y<b) y=b;
	if (y<c) y=c;
	if (y<d) y=d;
	return y-x;
}
ll get(int i,int x,int y)
{
	if (x==0 || x==i || y==n || y==i) return (1ll<<60);
	return calc(sum[x],sum[i]-sum[x],sum[n]-sum[y],sum[y]-sum[i]);
}
int main()
{
	#ifdef Kay
		freopen ("code.in","r",stdin);
		freopen ("code.out","w",stdout);
	#endif
	cin>>n;
	int i,j,k,l;
	for (i=1;i<=n;i++)
	scanf ("%lld",&a[i]),sum[i]=sum[i-1]+a[i];
	for (i=2,j=1;i<=n;i++)
	{
		while (j+1<i && sum[j+1]<sum[i]-sum[j+1]) j++;
		p1[i]=j;
	}
	for (i=n-1,j=n;i>=1;i--)
	{
		while (j-1>i && sum[j-2]-sum[i-1]>sum[n]-sum[j-2]) j--;
		p2[i]=j;
	}
	ll ans=1ll<<60;
	for (i=2;i<=n-2;i++)
	{
		ans=min(ans,get(i,p1[i],p2[i+1]-1)),ans=min(ans,get(i,p1[i],p2[i+1]-2));
		ans=min(ans,get(i,p1[i]+1,p2[i+1]-1)),ans=min(ans,get(i,p1[i]+1,p2[i+1]-2));
	}
	//for (i=1;i<=n;i++)
	//for (j=i+1;j<=n;j++)
	//for (k=j+1;k<n;k++)
	//if (get(j,i,k)==36) printf ("%d %d %d\n",i,j,k);
	printf ("%lld",ans);
	return 0;
}


Measured memory_bytes: 4992
#![allow(unused_imports)]
use std::cmp::max;
use std::num;
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        a: i32,
        b: i32,
    }
    if (a + b) % 2 == 1 {
        println!("IMPOSSIBLE");
    } else {
        println!("{}", (a + b) / 2);
    };
}


Measured memory_bytes: 4352
#include <string>
#include <vector>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <functional>
#include <utility>
#include <numeric>
#include <map>
#include <deque>
#include <queue>
#include <tuple>
using namespace std;

#define prec(i) cout << fixed << setprecision(i)

void outPut_YN(bool isYes) {
	if (isYes)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}

const long long MOD = 1000000007;

long long fact(long long k) {
	long long sum = 1;
	for (long long i = 2; i <= k; i++)
		sum *= i;

	return sum;
}

long long fact_mod(long long k) {
	long long sum = 1;
	for (long long i = 2; i <= k; i++)
		sum = (sum * i) % MOD;

	return sum;
}

int ctoi(char c) {
	if (c >= '0' && c <= '9')
		return c - '0';
	else
		return -1;
}

long long pow_mod(int a, int b) {
	long long ans = 1;
	for (int i = 0; i < b; i++)
		ans = (ans * a) % MOD;

	return ans;
}

long long powll(long long a, long long  b) {
	long long ans = 1;
	for (long long i = 0; i < b; i++)
		ans = ans * a;

	return ans;
}

long long modinv(long long a) {

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

	return u;
}

long long _gcd(long long a, long long b)
{
	if (a < b)
		swap(a, b);

	if (a % b == 0)
		return b;
	else
		return _gcd(b, a % b);
}

long long _lcm(long long a, long long b)
{
	return (((a * b) % MOD) * modinv(_gcd(a, b))) % MOD;
}

long long ncr(long long n, long long r) {
	long long sum = 1;
	for (long long i = r + 1; i <= n; i++)
		sum *= i;

	return sum;
}



int main()
{

	long long x, a, d, ans = 0, dir = 0;
	cin >> x >> a >> d;

	long long cnt = abs(ceil(abs(x) / (double)d));

	if (x < 0)
		d *= -1;

	if(a < cnt)
		ans = x - d * a;
	else {
		if((a - cnt) % 2 == 0)
			ans = x - d * cnt;
		else
			ans = x - d * (cnt - 1);
	}
	cout << abs(ans) << endl;

	return 0;
}

Measured memory_bytes: 3672
#include <bits/stdc++.h>
#define pb push_back
#define int long long
#define mp make_pair
#define inf 1000000007
#define LINF 1000000000000000007LL
#define ll long long
using namespace std;
double dist[1140][1140];
double ans[1140];
signed main(){
	int xs,xt,ys,yt;
	cin>>xs>>ys>>xt>>yt;
	int n;
	cin>>n;
	vector<int> x,y,r;
	for(int i=0;i<n;i++){
		int t1,t2,t3;
		cin>>t1>>t2>>t3;
		x.pb(t1);y.pb(t2),r.pb(t3);
	}
	x.pb(xs);y.pb(ys);r.pb(0);
	x.pb(xt);y.pb(yt);r.pb(0);
	for( int i = 0; i < n+2; i++){
		for(int j = 0; j < n + 2 ; j++ ){
			double xi = 1.0 * x[i], xj = 1.0 * x[j], yi = 1.0 * y[i], yj = 1.0 * y[j], ri = 1.0 * r[i], rj = 1.0*r[j];
			dist[i][j] = sqrt( (xi-xj) * (xi-xj) + (yi-yj) * (yi-yj) ) - ri - rj;
			dist[i][j] = max(0.0,dist[i][j]);
		}
	}
	for(int i = 0; i < n+2 ; i++){
		ans[i] = 1.0 * LINF;
	}
	ans[n] = 0.0;
	priority_queue< pair<double,int> , vector<pair<double,int> >, greater< pair<double,int> > > que;
	que.push( mp(ans[n],n) );
	while(!que.empty()){
		pair< double,int > di = que.top(); que.pop();
		for(int i=0;i<n+2;i++){
			if( di.second != i ){
				if( ans[i] > ans[di.second] + dist[di.second][i] ){
					ans[i] = ans[di.second] + dist[di.second][i];
					que.push( mp(ans[i],i) );
				}
			}
		}
	}
	cout<<setprecision(14)<<ans[n+1]<<endl;
	return 0;
}

Measured memory_bytes: 15228
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
	char c=getchar();bool f=0;x=0;
	while(!isdigit(c)) f|=c=='-',c=getchar();
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	if(f) x=-x;return x;
}
template<class t,class ...A> inline void read(t &x,A &...a){
	read(x);read(a...);
}
template<class t> inline void write(t x){
	if(x<0) putchar('-'),write(-x);
	else{if(x>9) write(x/10);putchar('0'+x%10);}
}

const int mod=998244353,N=1e5+5;
int n,cnt[3][600],pw[N*3],ans,sg[N],v[N],tag,m,big;
vector<int> g[N];

int mex(vector<int> &a){
	tag++;
	for(int x:a) v[x]=tag;
	for(int i=0;;i++) if(v[i]^tag) return i;
}

void dfs(int x){
	vector<int> tp;
	for(int y:g[x]){
		if(sg[y]==-1) dfs(y);
		tp.push_back(sg[y]);
	}
	sg[x]=mex(tp);
}

void init(int T){
	read(m);
	for(int i=1;i<=n;i++) g[i].clear(),sg[i]=-1;
	for(int i=1,x,y;i<=m;i++){
		read(x,y);
		if(x>y) swap(x,y);
		g[x].emplace_back(y);
	}
	for(int i=1;i<=n;i++) if(sg[i]==-1) dfs(i);
	for(int i=1;i<=n;i++) cnt[T][sg[i]]=(cnt[T][sg[i]]+pw[i])%mod;
}

signed main(){
	read(n);
	pw[0]=big=1;
	for(int i=1;i<=18;i++) big=10ll*big%mod;
	for(int i=1;i<=3*n;i++) pw[i]=1ll*pw[i-1]*big%mod;
	for(int i:{0,1,2}) init(i);
	for(int i=0;i<512;i++) for(int j=0;j<512;j++)
		ans=(ans+1ll*cnt[0][i]*cnt[1][j]%mod*cnt[2][i^j])%mod;
	write(ans);
}

Measured memory_bytes: 10096
#include<iostream>
#include<vector>
#include<map>

using namespace std;


int main() {
	int a[9];
	int n;

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

	for (int i = 0; i < n; i++) {
		int input_num;
		cin >> input_num;
		for (int j = 0; j < 9; j++) {
			if (a[j] == input_num) a[j] = 0;
		}
	}
	

	for (int i = 0; i < 3; i++) {
		int tmp = { 0 };
		int tmp2 = { 0 };

		for (int j = 0; j < 3; j++) {
			tmp += a[j + i * 3];
			tmp2 += a[j * 3 + i];
		}
		if (tmp * tmp2 == 0) {
			cout << "Yes" << endl;
			return 0;
		}
	}

	if ((a[0] + a[4] + a[8]) == 0) {
		cout << "Yes" << endl;
		return 0;
	}
	else if ((a[2] + a[4] + a[6]) == 0) {
		cout << "Yes" << endl;
		return 0;
	}

	cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    ll N;
    ll C[4];
    cin >> C[0];
    int i;
    for(i = 1; i < 4; i++){
        cin >> C[i];
        C[i] = min(C[i],2*C[i-1]);
    }
    cin >> N;
    ll ans = 0; ll size = 2;
    while(N != 0){
        ans += ((ll)(N/size)*C[--i]);
        N %= size;
        size /= 2;
    }
    cout << ans << "\n";
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main() {
	int a, b, c, d, e;
	int K;
	cin >> a >> b >> c >> d >> e >> K;
	if (e - a <= K) {
		cout << "Yay!" << endl;
	}
	else {
		cout << ":(" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a;
    int b;
  int aa,bb;
    cin>>a>>b;
  	aa=min(a,b);
    bb=max(a,b);
  	if(aa==1&&bb==2)cout<<3<<endl;
  	if(aa==2&&bb==3)cout<<1<<endl;
  	if(aa==1&&bb==3)cout<<2<<endl;
	return 0;
}

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

int main()
{
    long long N;
    cin>>N;
    vector<long long> A(N);
    for (long long &a: A)
        cin>>a;

    long long M = 1000000007LL;
    long long ans = 0;
    for (long long d=0; d<60; d++)
    {
        long long c = 0;
        for (long long a: A)
            c += a>>d&1;
        ans += (1LL<<d)%M*c%M*(N-c)%M;
        ans %= M;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 2560
#include <iostream>
using namespace std;
typedef long long ll;

ll gcd(ll n, ll m){
    if(n % m == 0) return m;
    return gcd(m, n % m);
}

int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i++){
        ll a, b, c, d;
        cin >> a >> b >> c >> d;
        if(b > d || b > a){
            cout << "No" << endl;
            continue;
        }
        if(c > b){
            cout << "Yes" << endl;
            continue;
        }
        ll g = gcd(b, d);
        if(((a - b) / g + 1) * g < a - c) cout << "No" << endl;
        else cout << "Yes" << endl;
    }
}

Measured memory_bytes: 256
#include<atcoder/all>
#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--)
using namespace std;
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const int MOD2 = 998244353;

int n, q, u, v;
int main() {
    std::cin >> n >> q;
    atcoder::dsu d(n);
    rep(i, q) {
        std::cin >> n >> u >> v;
        if(n)
            std::cout << d.same(u, v) << std::endl;
        else
            d.merge(u, v);
    }
    return 0;
}

Measured memory_bytes: 3952