akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define FOR(e, c) for (auto &e : c)
#define SORT(v, n) sort(v, v + n);
#define vsort(v) sort(v.begin(), v.end());
#define rvisort(v) sort(v.begin(), v.end(), greater<int>());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define int long long
#define PI (acos(-1))

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using ul = unsigned long;

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

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

int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
int LCM(int a, int b) { return a * b / GCD(a, b); }

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  
  int n;
  cin>>n;
  vi L(n);
  rep(i,n) cin>>L[i];
  vsort(L);
  
  int ans=0;
  rep(i,n){
    for(int j=i+1;j<n;j++){
      for(int k=j+1;k<n;k++){
        if(L[i]+L[j]>L[k]) ans++;
      }
    }
  }
  cout(ans);
}

Measured memory_bytes: 256
package main

import (
  "bufio"
  "fmt"
  "os"
  "strconv"
  "strings"
)

func main() {
  var n,k int = NextInts()
  var a []int = NextIntArray()
  var r []int64 = make([]int64,n+1)
  for i:=n-1;i>-1;i-- {
    r[i] = r[i+1]
    if a[i] > 0 { r[i] += int64(a[i]) }
  }
  var s,t int64
  for i:=0;i<k;i++ { t += int64(a[i]) }
  var m int64 = r[k]
  if m < t+r[k] { m = t+r[k] }
  for i:=0;i<n-k;i++ {
    if a[i] > 0 { s += int64(a[i]) }
    t += int64(a[i+k]-a[i])
    if m < s+r[i+k+1] { m = s+r[i+k+1] }
    if m < s+t+r[i+k+1] { m = s+t+r[i+k+1] }
  }
  fmt.Println(m)
}

var reader = bufio.NewReaderSize(os.Stdin,1000000)
func NextLine() string {
  var line,buffer []byte
  var isPrefix bool = true
  var err error
  for ;isPrefix; {
    line,isPrefix,err = reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer,line...)
  }
  return string(buffer)
}
func NextInts() (int,int) {
  var s []string = strings.Split(NextLine()," ")
  n,_ := strconv.Atoi(s[0])
  k,_ := strconv.Atoi(s[1])
  return n,k
}
func NextIntArray() []int {
  var s []string = strings.Split(NextLine()," ")
  var a []int = make([]int,len(s))
  for i:=0;i<len(s);i++ { a[i],_ = strconv.Atoi(s[i]) }
  return a
}

Measured memory_bytes: 7424
#include <iostream>
#include <string>
#include <set>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;
int main(){
    int a, b, c, maxi, m, mini;
    cin >> a >> b >> c;
    maxi = max(a, max(b, c));
    if(maxi == a){
        cout << maxi * 10 + b + c << endl;
    }
    else if(maxi == b){
        cout << maxi * 10 + a + c << endl;
    }
    else{
        cout << maxi * 10 + a + b<< endl;
    }
}

Measured memory_bytes: 256
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define DB double
#define SG string
#define LL long long
#define Fp(A,B,C,D) for(A=B;A<=C;A+=D)
#define Fm(A,B,C,D) for(A=B;A>=C;A-=D)
#define Clear(A) memset(A,0,sizeof(A))
using namespace std;
const LL Mod=1e9+7;
const LL Max=1e2+5;
const LL Inf=1e18;
char CH[Max];
LL N,Ans,Cnt,Cnt1[Max],Cnt2[Max];
inline LL Read(){
	LL X=0;char CH=getchar();bool F=0;
	while(CH>'9'||CH<'0'){if(CH=='-')F=1;CH=getchar();}
	while(CH>='0'&&CH<='9'){X=(X<<1)+(X<<3)+CH-'0';CH=getchar();}
	return F?-X:X;
}
inline void Write(LL X){
	if(X<0)X=-X,putchar('-');
	if(X>9)Write(X/10);
	putchar(X%10+48);
}
int main(){
	LL I,J,K;
	N=Read();scanf("%s",CH+1);
	Fp(I,2,N-1,1){
		Clear(Cnt1);Clear(Cnt2);Cnt=0;
		Fp(J,1,I-1,1){
			Cnt1[CH[J]-'a'+1]++;
		}
		Fp(J,I,N,1){
			Cnt2[CH[J]-'a'+1]++;
		}
		Fp(J,1,30,1){
			if(Cnt1[J]!=0&&Cnt2[J]!=0){
				Cnt++;
			}
		}Ans=max(Cnt,Ans);
	}Write(Ans);
	return 0;
}

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

int main()
{
    int n,num,flag=0;
    cin >> n;
    while(n--){
        cin >> num;
        if(num%2==0){
            if(num%5&&num%3){
                flag=1;
            }
        }
    }
    if(!flag)
        cout << "APPROVED"<<endl;
    else
        cout << "DENIED";
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define inf 1<<30
#define il inline 
#define in1(a) read(a)
#define in2(a,b) in1(a),in1(b)
#define in3(a,b,c) in2(a,b),in1(c)
#define in4(a,b,c,d) in2(a,b),in2(c,d)
il void readl(ll &x){
    x=0;ll f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
il void read(int &x){
    x=0;int f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
using namespace std;
/*===================Header Template=====================*/
#define N 100010
int main(){
 	int a,b;
 	in2(a,b);
	printf("%d",a*b-a-b+1);
	return 0; 
}


Measured memory_bytes: 128
//
//  main.cpp
//  SPG-B
//

#include <iostream>
#include<vector> // 配列を使う
using namespace std;
int main(int argc, const char * argv[]) {
    int N;
    long K;
    long mod=1000000000+7;
    cin >> N>>K;
    vector<int> A(N);
    for (int i=0; i<N; i++) {
        cin >> A.at(i);
    }
    long ans0=0;
    for (int j=0; j<N; j++) {
        for (int k=j+1; k<N; k++) {
            if (A.at(j)>A.at(k)) {
                ans0++;
            }
        }
    }
    long ans1=0;
    for (int m=0; m<N; m++) {
        for (int p=0; p<N; p++) {
            if (A.at(m)>A.at(p)) {
                ans1++;
            }
        }
    }
    ans0 *= K%mod;
    //ans1 = (K*(K-1)/2)%mod*(ans1%mod);
    ans1=(ans1%mod)*((K*(K-1)/2)%mod);
    long ans=ans0+ans1;
    cout << ans%mod << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <cstring>
#include <functional>
using namespace std;
typedef long long ll;
typedef pair<long long, long long> P;
#define rep(i, n) for(long long i=0; i<n; i++)
#define reps(i, s, e) for(long long i=s; i<e; i++)
#define repr(i, n) for(long long i=n-1; i>=0; i--)
#define reprs(i, s, e) for(long long i=e-1; i>=s; i--)

int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);

    string s; cin >> s;

    if(s == "ABC"){
        cout << "ARC" << endl;
    }
    if(s == "ARC"){
        cout << "ABC" << endl;
    }

    return 0;
}

Measured memory_bytes: 3656
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <string>
#include <math.h>
#include <cstdlib>
#include <istream>
#include <sstream>
#include <cctype>
#define fore(i,x,y) for(long long i=x;i<y;i++)
typedef long long ll;
using namespace std;

void cinv(vector<ll> &V){
	ll t;
	cin >> t;
	V.push_back(t);
}

int main()
{
	ll A,B;
	vector<ll> ANS;
	cin >> A >> B;
	ANS.push_back(A+B);
	ANS.push_back(A-B);
	ANS.push_back(A*B);
	sort(ANS.begin(),ANS.end());
	cout << *(ANS.end()-1) << endl;
}

Measured memory_bytes: 256
import java.util.*;
import java.math.*;
import java.awt.geom.*;
import java.io.*;
    
    
public class Main {
	static int N;
	static int M;
	static int K;
	static int P;
	static int[][] dp;
	static int[] s;
	static int[] t;
	static int INF = 2 << 27;
	static int CHECK;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		K = sc.nextInt();
		P = sc.nextInt();
		dp = new int[N][N];
		for(int i = 0; i < N; i++) {
			Arrays.fill(dp[i], INF);
			dp[i][i] = 0;
		}
		for(int i = 0; i < M; i++) {
			int x = sc.nextInt()-1;
			int y = sc.nextInt()-1;
			int w = sc.nextInt();
			dp[x][y] = w;
			dp[y][x] = w;
		}
		s = new int[K];
		t = new int[K];
		for(int i = 0; i < K; i++) {
			s[i] = sc.nextInt()-1;
			t[i] = sc.nextInt()-1;
		}
		for(int i = 0; i < K; i++) {
			CHECK |= 1 << i;
		}
		
		for(int k = 0; k < N; k++) {
			for(int i = 0; i < N; i++) {
				for(int j = 0; j < N; j++) {
					if(dp[i][j] > dp[i][k] + dp[k][j]) {
						dp[i][j] = dp[i][k] + dp[k][j];
					}
				}
			}
		}
		int ans = dfs(P-1,0,0,0);
		
		if(ans == INF) {
			System.out.println("Cannot deliver");
		}
		else {
			System.out.println(ans);
		}
	}
	static int dfs(int now, int sS, int tS,int cost) {
		if(sS == CHECK && tS == CHECK) return cost;
		int ret = INF;
		for(int i = 0; i < s.length; i++) {
			if((sS & 1 << i) != 0 || dp[now][s[i]] == INF) continue;
			ret = Math.min(ret, dfs(s[i],sS | 1 << i,tS,cost + dp[now][s[i]]));
		}
		for(int i = 0; i < t.length; i++) {
			if((tS & 1 << i) != 0 || (sS & 1 << i) == 0 || dp[now][t[i]] == INF) continue;
			ret = Math.min(ret, dfs(t[i],sS,tS | 1 << i,cost + dp[now][t[i]]));
		}
		return ret;
	}
}

Measured memory_bytes: 41812
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<map>
#include<unordered_map>
#include<functional>
#include<set>
#include<numeric>

#pragma region
using namespace std;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define rep(i,n) FOR(i,0LL,n)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define rrep(i,n) RFOR(i,0LL,n)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define COUNT(a,y,x) upper_bound(all(a), y) - lower_bound(all(a), x)
#define UNIQUE(a) sort(all(a)); a.erase(unique(all(a)), a.end())
#define SUM(a) accumulate(all(a),0LL)
#define pb push_back
#define endl '\n'
typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<string> vs;
typedef map<ll, ll> MAP;
const ll inf = 2222222222222222222LL;
const ll mod = 1000000007LL;

ll n = 0, m = 0, ans = 0, cnt = 0, tmp = 0, ma = -inf, mi = inf;
string s;
bool ok = true, flag = false;
ll dx[9] = { 0,1,-1,0,0,1,1,-1,-1 }, dy[9] = { 0,0,0,1,-1,1,-1,1,-1 };
#pragma endregion
#define MAX 222222




int main(void) {


  cin >> n >> m;
  vll a;
  rep(i, n) {
    cin >> tmp;
    a.pb(tmp);
  }
  sort(all(a));
  ans = inf;
  rep(i, n - m + 1) {
    ans = min(ans, a[i + m - 1] - a[i]);
  }
  cout << ans << endl;



  return 0;
}

Measured memory_bytes: 1400
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")

#include <bits/stdc++.h>

using namespace std;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "


// CHECK THE LIMITS
typedef long long ll;

const int MOD = 1000000007;
const ll INFLL = 1e18;
const int INF = 1e9;
const int NMAX = 303;

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

double dp[NMAX][NMAX][NMAX];
double ev[NMAX][NMAX][NMAX];

// dp[a][b][c] = the expected number of operation so far to get to state(a,b,c)
// p-bility of getting to this state at all


// ev[a][b][c] expected value

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> cnt(4);

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

    dp[cnt[1]][cnt[2]][cnt[3]] = 1;

    for(int c = n; c >= 0; --c)
    {
        for(int b = n; b>= 0; --b)
        {
            for(int a = n; a>=0; --a)
            {
                // dp[a][b][c]
                if(a == 0 && b == 0 && c == 0)
                    continue;

                if(a+b+c > n)
                    continue;

                double p_waste = (double) (n - (a+b+c)) / n;
                double ev_waste = p_waste / (1- p_waste);
                ev[a][b][c] += ev_waste * dp[a][b][c];

                // remove 1 -> dp[a-1][b][c]
                if(a != 0)
                {
                    double p_go = (double) a / (a+b+c);
                    dp[a-1][b][c] += dp[a][b][c] * p_go;
                    ev[a-1][b][c] += ev[a][b][c] * p_go; 
                }
                // remove 2 -> dp[a+1][b-1][c]
                if(b != 0){
                    double p_go = (double) b / (a+b+c);
                    dp[a+1][b-1][c] += dp[a][b][c] * p_go;
                    ev[a+1][b-1][c] += ev[a][b][c] * p_go; 
                }
                // remove 3 -> dp[a][b+1][c-1]
                if(c != 0){
                    double p_go = (double)c / (a+b+c);
                    dp[a][b+1][c-1] += dp[a][b][c] * p_go;
                    ev[a][b+1][c-1] += ev[a][b][c] * p_go; 
                } 
            }
        }
    }
    cout  << fixed << setprecision(10) << ev[0][0][0] + cnt[1] + 2 * cnt[2] + 3*cnt[3];


    return 0;
}

Measured memory_bytes: 434432
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int INF = 1000000000;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define rep(i,n) REP(i, 0, n)
int main(){
    int n;
    while(cin >> n && n){
        int k = n / 2 + 1;
        int ans = 0;
        REP(i, 1, k){
            int sum = i;
            REP(j, i + 1, k + 1){
                sum += j;
                if(sum == n){
                    ans++;
                    break;
                }else if(sum > n){
                    break;
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int > h;
vector<long> cost;


long solve(int i){
	if(i==0){
		cost[i]=0;
		return cost[i];
	}
	else if(i==1){
		cost[i]=abs(h[1]-h[0]);
	}
	else if(cost[i]!=-1)
		return cost[i];
	else{
		cost[i]=min(abs(h[i-1]-h[i])+solve(i-1),(abs(h[i-2]-h[i])+solve(i-2)));
		return cost[i];
	}

}


	
int main(){
	cin>>n;
	h.assign(n,0);
	for(int i=0;i<n;i++){
		cin>>h[i];
	}
	cost.assign(n,-1);
	cout<<solve(n-1);
	return 0;
}



Measured memory_bytes: 4480
#include <bits/stdc++.h>
#define sort stable_sort
using namespace std; 

int _;

int a,b;

int main()
{
	scanf("%d%d",&a,&b);
	printf((a+b)%3 && a%3 && b%3 ?"Impossible\n":"Possible\n");
	return 0;
}



Measured memory_bytes: 3712
#include <algorithm>
#include <string.h>
#include <iostream>
#include <stdio.h>
#include <math.h>

using namespace std;

typedef long long ll;
typedef double db;

int main() {
	ll a, v, b, w, t;
	cin >> a >> v;
	cin >> b >> w;
	cin >> t;

	ll ta = a - b;
	ll tb = v * t + a - (w * t + b);

	if (a < b) {
		if (b - a <= t * (v - w)) {
			cout << "YES" << endl;
			return 0;
		}
	}
	else {
		if (a - b <= t * (v - w)) {
			cout << "YES" << endl;
			return 0;
		}
	}
	/*
	if ((ta >= 0 && tb <= 0) || (ta <= 0 && tb >= 0)) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
	*/

	cout << "NO" << endl;

	return 0;
}
//	if (llabs(a - b) <= t * (v - w)) {

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

#define FORE(i, a) for (auto i = a.begin(); i != a.end(); ++i)
#define REPU(i, a, b) for (int i = (a); i < (b); ++i)
#define REPD(i, a, b) for (int i = (a); i > (b); --i)
#define MEM(a, x) memset(a, x, sizeof(a))
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())

vector<string> split(const string &s, char c) {
	vector<string> v; stringstream ss(s); string x;
	while (getline(ss, x, c)) v.push_back(x);
	return v;
}
#define DEBUG(args...) { vector<string> _v = split(#args, ','); err(_v.begin(), args); }
void err(vector<string>::iterator it) {}
template<typename T, typename... Args>
void err(vector<string>::iterator it, T a, Args... args) {
	cerr << "[DEBUG] " << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << '\n';
	err(++it, args...);
}

typedef long long ll;
const int MOD = 1000000007;

template<class T, class U> inline T tmin(T a, U b) { return (a < b) ? a : b; }
template<class T, class U> inline T tmax(T a, U b) { return (a > b) ? a : b; }
template<class T, class U> inline void amax(T &a, U b) { if (b > a) a = b; }
template<class T, class U> inline void amin(T &a, U b) { if (b < a) a = b; }
template<class T> T gcd(T a, T b) { while (b != 0) { T c = a; a = b; b = c % b; } return a; }

int main(int argc, char *argv[]) {
	ios_base::sync_with_stdio(false);

	int x, y; cin >> x >> y;
	int ans = INT_MAX;
	if (y == 0) {
		if (x == 0) ans = 0;
		else if (x > 0) ans = x + 1;
		else ans = -x;
		cout << ans << endl;
		return 0;
	}
	if (x >= 0 && y >= 0) {
		if (y >= x) amin(ans, y - x);
		else amin(ans, 2 + abs(y - x));
	}
	else if (x >= 0 && y <= 0) {
		if (abs(y) >= x) amin(ans, 1 + abs(y) - x);
		else amin(ans, 1 + x - abs(y));
	}
	else if (x <= 0 && y >= 0) {
		if (abs(x) >= y) amin(ans, 1 + abs(x) - y);
		else amin(ans, 1 + y - abs(x));
	}
	else {
		if (x <= y) amin(ans, y - x);
		else amin(ans, 2 + x - y);
	}
	cout << ans << endl;

	return 0;
}


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

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

  vector<int> d(N);
  for (int i = 0; i < N; i++)
    cin >> d.at(i);

  sort(d.begin(), d.end());

  int u = d.at(N / 2);
  int l = d.at(N / 2 - 1);

  cout << u - l << endl;
}

Measured memory_bytes: 640
#include <stdio.h>
#include <string.h>

int main(){
   char s[1001],t[1001];
   int ans,i,j,k,ls,lt;

   scanf("%s",s);
   scanf("%s",t);
   ls=strlen(s);lt=strlen(t);
   ans=lt+1;
   for (i=0;i<ls-lt+1;i++) {
      for (j=k=0;j<lt;j++)
         if (s[i+j]!=t[j]) k++;
      if (k<ans) ans=k;
   }
   printf("%d\n",ans);
   return 0;
}


Measured memory_bytes: 1732
#include <iostream>
using namespace std;
bool L[5000][5000] = {}, R[5000][5000] = {};

int main() {
    int n, k; cin >> n >> k;
    int a[n]; for (int i = 0; i < n; i++) cin >> a[i];
    L[0][0] = true; if (a[0] < k) L[0][a[0]] = true;
    R[n-1][0] = true; if (a[n-1] < k) R[n-1][a[n-1]] = true;
    for (int i = 1; i < n-1; i++) {
        L[i][0] = true;
        for (int s = 1; s < k; s++)
            L[i][s] = L[i-1][s] || s >= a[i] && L[i-1][s-a[i]];
    }
    for (int i = n-2; i > 0; i--) {
        R[i][0] = true;
        for (int s = 1; s < k; s++) 
            R[i][s] = R[i+1][s] || s >= a[i] && R[i+1][s-a[i]];
    }
    int ans = 0;
    int v = k - a[0];
    if (v > 0) while (v < k) { if (R[1][v]) break; v++; }
    if (v == k) ans++;
    v = k - a[n-1];
    if (v > 0) while (v < k) { if (L[n-2][v]) break; v++; }
    if (v == k) ans++;
    for (int i = 1; i < n-1; i++) {
        v = k - a[i];
        int ls = 0, rs = k-1;
        while (rs >= 0 && !R[i+1][rs]) rs--;
        bool found = false;
        while (ls < k && rs >= 0) {
            if (v <= ls + rs && ls + rs < k) { found = true; break; }
            if (v > ls + rs) do ls++; while (ls < k && !L[i-1][ls]);
            else do rs--;  while (rs >= 0 && !R[i+1][rs]);
        }
        if (!found) ans++;
    }
    cout << ans << endl;
}


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

int main() {
	int n;
	cin>>n;
	int l[n],r[n];
	for(int i=0;i<n;i++){
		cin>>l[i]>>r[i];
	}
	int ir[100000];
	for(int i=0;i<100000;i++){
		ir[i]=1;;
	}
	ir[0]=0;
	ir[1]=0;

	for(int i=2;i<1000;i++){
		int mul=2;
		while(mul*i<100000){
			ir[mul*i]=0;
			mul++;
		}
	}
	int c[100000];
	c[0]=0;
	c[1]=0;
	c[2]=0;
	for(int i=3;i<100000;i++){
		if(ir[i]*ir[(i+1)/2]){
			c[i]=1;
		}else{
			c[i]=0;
		}
		c[i]+=c[i-1];
	}
	for(int i=0;i<n;i++){
		cout<<c[r[i]]-c[l[i]-1]<<endl;
	}
	return 0;
}


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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)    FOR (i,0,n)
#define ALL(f,x,...) ([&](decltype((x)) ALL) {\
return (f)(begin(ALL), end(ALL), ## __VA_ARGS__); })(x)

using namespace std;
using ll = int64_t;

const ll INF = 1000000000000001;

// 10進数の各桁の和
int getSum(ll N)
{
    int sm = 0;
    while (0 < N)
    {
        ll tmp = N % 10;
        sm += (int)tmp;
        N /= 10;
    }
    return sm;
}

// 末尾 9 を試す
// 123 なら 129 と 199
// S / S(n) の 商(整数) が同じなら
// 大きい数字を sunuke数 とする
ll getAll9(ll N)
{
    // 最小
    // n
    ll num = INF;

    // 最小
    // S / S(n)
    ll val = INF;

    ll tmp = N;
    int t = 0;
    ll all9 = 0;
    while (0 < tmp)
    {
        // 123 → 12
        tmp /= 10;

        t++;
        all9 = all9 * 10 + 9;

        // 最上位桁 そのまま
        // 0 ならば 最上位
        if (0 < tmp)
        {
            // 12 → 120 → 129
            ll now = tmp * pow(10, t) + all9;
            ll cal = now / (ll)getSum(now);

            if (cal <= val)
            {
                val = cal;
                num = now;
            }
        }
    }
    return num;
}

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

    ll N = 1;
    REP(i, K)
    {
        ll self = N;
        ll cal = self / (ll)getSum(N);

        ll a9 = getAll9(N);
        ll cal9 = a9 / (ll)getSum(a9);

        ll sunuke = self;
        if (cal9 < cal)
        {
            sunuke = a9;
            N = a9;
        }

        cout << sunuke << endl;

        N = sunuke;
        N++;
    }

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int arr[n], i, cnt=0;
    for(i=0; i<n; i++){
        cin >> arr[i];
    }
    for(i=0; i<n; i+=2){
        if(arr[i]%2==1)
            ++cnt;
            continue;
    }
    cout << cnt << endl;
}


Measured memory_bytes: 3480
/* *
 *
 * Author: Hamkor
 *
 * */
 
#include <bits/stdc++.h>

using namespace std;

/* * * *   * * *   	* * * */
typedef long long ll;
const int oo = 1e9;
const ll mod = 100000000;
typedef complex<ll> P;
#define X real()
#define Y imag()
/* * * *   * * *   	* * * */
int gcd(int a, int b){return b == 0? a: gcd(b, a%b);}
int main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	string s, x, y; cin>>s;
	x = y = s;
	int z = 0, o = 0;
	if(x[0] != '0'){x[0] = '0'; z++;}
	for (int i=1; i<(int)x.size(); ++i){
		if (x[i] == x[i-1]){
			x[i] = x[i-1] == '0' ? '1': '0';
			z++;
		}
	} 
	if(y[0] != '1'){y[0] = '1'; o++;}
	for (int i=1; i<(int)y.size(); ++i){
		if (y[i] == y[i-1]){
			y[i] = y[i-1] == '0' ? '1': '0';
			o++;
		}
	}
	cout<<min(z, o); 
	return 0;
}


Measured memory_bytes: 592
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=1e5+10;

void io(){
	ios::sync_with_stdio(0);
	cin.tie();
	cout.tie();
}

struct node{
	double x;
	double y;
}p[N];

bool cmp(node a,node b)
{
	return atan2(a.x,a.y)>atan2(b.x,b.y);
} 
int main()
{
	//io();
	int n;cin>>n;
	for(int i=0;i<n;i++)	cin>>p[i].x>>p[i].y;
	sort(p,p+n,cmp);
	double ans=0;
	for(int i=0;i<n;i++){
		double a=0,b=0;
		int now=i;
		do{
			a+=p[now].x;
			b+=p[now].y;
			ans=max(ans,a*a+b*b);
			if(now+1<n)now++;
			else now=0;
		}while(now!=i);
	}
	printf("%.15f\n",sqrt(ans));
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int,int>
#define pb push_back
#define F first
#define S second
#define mod 1000000007
#define maxn 105
#define boost ios::sync_with_stdio(false);cin.tie(0)
#define fr freopen("source.txt","r",stdin),freopen("output.txt","w",stdout)
#define SET(a,b) memset(a,b,sizeof(a))

ll w[maxn],v[maxn],dp[101][101][305];

int main(){
    boost;
    
    int n;
    ll W,s=0;
    cin>>n>>W;

    rep(i,1,n){
        cin>>w[i]>>v[i];
        s+=w[i];
    }

    if(W>=s){
        s=0;
        rep(i,1,n)s+=v[i];
        cout<<s;
        return 0;
    }

    ll m=w[1];
    rep(i,1,n)w[i]-=m;

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=0;k<301;k++){
                dp[i][j][k]=dp[i-1][j][k];
                if(k-w[i]>=0)dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k-w[i]]+v[i]);
            }
        }
    }

    ll ans=0;
    rep(i,1,n){
        rep(j,0,301)
        if(1ll*(j+1ll*i*m)<=W)ans=max(ans,dp[n][i][j]);
    }
    cout<<ans;

    return 0;
}

Measured memory_bytes: 24320
#! /usr/bin/env python3

import sys
stdin = sys.stdin
YES = "Yes"
NO = "No"
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()


s = list(ns())
n = len(s)
ss = s[:(n-1)//2]
sss = s[(n+3)//2-1:]
 
if s == list(reversed(s)) and ss == list(reversed(ss)) and sss == list(reversed(sss)):
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <string.h>
using namespace std; using ll = long long; using pll = pair<ll, ll>;
using vl = vector<ll>; using vll = vector<vl>; using vpll = vector<pll>;
int ctoi(char c) {
	switch (c) {
	case '0': return 0; case '1': return 1; case '2': return 2;
	case '3': return 3; case '4': return 4; case '5': return 5;
	case '6': return 6; case '7': return 7; case '8': return 8;
	case '9': return 9;  default: return 0;
	}
}
bool pairCompare(const pll firstElof, pll secondElof)
{
	return firstElof.first > secondElof.first;
}
//**Snippetリスト**//
//rep, vin, all, iteLoop//
//gcdlcm, isPrime, eratos, modinv, bitSearch, bitList, dfs, bfs, dijkstra, UnionFind, COM, digitDP//
ll i, j, k, l; ll N, M, K, H, W, L;
ll MOD = 1000000007; ll INF = 9999999999999; ll ans = 0;
vl flag, color; vll path; vl D; ll C;
//***********//
int main() {
	cin >> N;
	vl A(N);
	ll two = 0;
	ll four = 0;
	for (i = 0; i < N; i++) {
		cin >> A[i];
		if (A[i] % 4 == 0) {
			four++;
		}
		else if (A[i] % 2 == 0) {
			two++;
		}
	}
	if (four * 2 + two >= N || four*2+1>=N) {
		cout << "Yes";
	}
	else {
		cout << "No";
	}
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;

#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (ll i = (l); i < (r); i++)
#define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--)
#define repa(i,n) for (auto& i: n)

template<class T> inline bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
void init() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);}

#ifdef DEBUG
template <class T, class N> void verr(const T& a, const N& n) { rep(i, n) cerr << a[i] << " "; cerr << "\n" << flush; }
ll dbgt = 1; void err() { cerr << "passed " << dbgt++ << "\n" << flush; }
template<class H, class... T> void err(H&& h,T&&... t){ cerr<< h << (sizeof...(t)?" ":"\n") << flush; if(sizeof...(t)>0) err(forward<T>(t)...); }
#endif

const ll INF = 5e18;
const ld EPS = 1e-11;
const ld PI = acos(-1.0L);
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
//--------------------------------------------------------------------------------//
ll A[200005];
int main() {
    init();
    string S;
    cin >> S;
    reverse(all(S));

    ll v = 0, p = 1, m = 2019;
    rep(i,S.size()){
        (v += (S[i] - '0')*p) %= m;
        A[i] = v;
        (p *= 10) %= m;
    }
    // verr(A, 20);

    map<ll, ll> mp;
    mp[0]++;
    ll ans = 0;
    rep(i,S.size()){
        ans += mp[A[i]];
        mp[A[i]]++;
    }

    cout << ans << endl;
}

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

using namespace std;

int main() {
    int n;
    cin >> n;
    int cnt = 0;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        if (a == 1) {
            ++cnt;
        } else {
            cnt = 0;
        }
        ans = max(ans, cnt);
    }
    cout << ans + 1 << '\n';
}


Measured memory_bytes: 3084
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <queue>
#include <stack>

using namespace std;

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

const ll mod = 1000000007;

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

  ll t1, t2;
  cin >> t1 >> t2;
  ll a1, a2;
  cin >> a1 >> a2;
  ll b1, b2;
  cin >> b1 >> b2;

  ll as = t1 * a1 + t2 * a2;
  ll bs = t1 * b1 + t2 * b2;
  if (as == bs) {
    cout << "infinity" << endl;
    return 0;
  }

  ll as1 = t1 * a1;
  ll as2 = t2 * a2;
  ll bs1 = t1 * b1;
  ll bs2 = t2 * b2;
  if (as1 > bs1) {
    if (as > bs) {
      cout << 0 << endl;
      return 0;
    }
  }
  else if (bs1 > as1) {
    if (bs > as) {
      cout << 0 << endl;
      return 0;
    }
  }

  ll diff1 = as1 - bs1;
  ll diff2 = bs2 - as2;
  if (diff1 < 0) diff1 = -diff1;
  if (diff2 < 0) diff2 = -diff2;
  ll delta = diff1 - diff2;
  if (delta < 0) delta = -delta;
  ll ans = 0;
  ans += ((diff1 / delta) + 1) * 2 - 1;
  if (diff1 % delta == 0) ans -= 1;
  
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _USE_MATH_DEFINES
#define ios std::ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define PI acos(-1.0) //3.14159265358
#define EPS 1e-9 //epsilon, 10^-9, checking for equality 
#define pb push_back
#define fi first
#define se second
#define sz(x) x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define isort(x) sort(x.begin(),x.end())
#define dsort(x) sort(x.rbegin(),x.rend())
const int inf=1e9+7; //10^9 +7
const int modc=998244353;
typedef long long int ll;typedef vector<int> vi;typedef vector<ll> vll;
typedef pair<int,int> ii;typedef map<int,int> mii;
inline void rvi(vi &v, int n){int temp; rep(i,n){cin>>temp;v.pb(temp);}}
inline void rvll(vll &v, int n){ll temp;rep(i,n){cin>>temp;v.pb(temp);}}
inline void prvi(vi &a){rep(i,sz(a)){cout<<a[i]<<" ";}cout<<endl;}
inline void prvll(vll &a){rep(i,sz(a)){cout<<a[i]<<" ";}cout<<endl;}
inline vll prefixsum(vi &a){vll b;b.pb(a[0]);for(int i=1;i<sz(a);i++){b.pb(a[i]+b[i-1]);}return b;}
inline vll suffixsum(vi &a){vll b(sz(a));b[sz(a)-1]=a[sz(a)-1];for(int i=sz(a)-2;i>=0;i--){b[i]=a[i]+b[i+1];}return b;}
inline vll prefixsum(vll &a){vll b;b.pb(a[0]);for(int i=1;i<sz(a);i++){b.pb(a[i]+b[i-1]);}return b;}
inline vll suffixsum(vll &a){vll b(sz(a));b[sz(a)-1]=a[sz(a)-1];for(int i=sz(a)-2;i>=0;i--){b[i]=a[i]+b[i+1];}return b;}
int dx[4]={1,0,-1,0}, dy[4]={0,1,0,-1};
void solve();int main(){ios;solve();return 0;}
//--------SOLVE--------------------------------------------------------------------
long double dp[3001][3001];
void solve()
{
	int n;cin>>n;
	vector<double> p(n+1);
	rep(i,n) cin>>p[i+1];
	//dp[i][j] represents prob of getting j heads in 1 to i denominatinos
	rep(i,n+1) dp[0][i]=0.0;
	dp[0][0]=1.0;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=i;j++)
		{
			dp[i][j]=dp[i-1][j]*((double)1-p[i]);
			if(j>0)
				dp[i][j]+=dp[i-1][j-1]*(p[i]);
		}
	}
	long double ans=0.0;
	for(int i=n/2+1;i<=n;i++)
	{
		ans+=dp[n][i];
	}
	cout<<fixed<<setprecision(15)<<ans<<endl;
}

Measured memory_bytes: 139136
import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Read as T

main :: IO ()
main = do
  x <- unsafeTextToInt <$> T.getLine :: IO Int
  print . fst . until ((x <=) . snd) ((,) <$> succ . fst <*> ((+) <$> id <*> (`div` 100)) . snd) $ (0, 100)

unsafeTextToInt :: T.Text -> Int
unsafeTextToInt s = case T.signed T.decimal s of
  Right (n, _) -> n


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

#define MAX 10000
#define INFTY (1<<29)

class DisjointSet{
public:
	vector<int> rank,p;
	DisjointSet(){}
	DisjointSet(int size){
		rank.resize(size,0);
		p.resize(size,0);
		for (int i = 0; i < size; ++i) {makeSet(i);}
	}
	void makeSet(int x){
		p[x]=x;
		rank[x]=0;
	}
	bool same(int x, int y){
		return findSet(x)==findSet(y);
	}
	void unite(int x,int y){
		link(findSet(x),findSet(y));
	}
	void link(int x,int y){
		if (rank[x]>rank[y]){
			p[y]=x;
		}else{
			p[x]=y;
			if(rank[x]==rank[y]){
				rank[y]++;
			}
		}
	}
	int findSet(int x){
		if(x!=p[x]){
			p[x]=findSet(p[x]);
		}
		return p[x];
	}
};

class Edge{
public:
	int source,target,cost;
	Edge(int source=0,int target=0,int cost=0):
		source(source),target(target),cost(cost){}
	bool operator < (const Edge &e) const{
		return cost < e.cost;
	}
};

int kruskal(int N,vector<Edge> edges){
	int totalCost=0;
	sort(edges.begin(),edges.end());
	DisjointSet dset=DisjointSet(N+1);
	for (int i = 0; i < N; ++i) {dset.makeSet(i);}
	int source,target;
	for (int i = 0; i < edges.size(); ++i) {
		Edge e=edges[i];
		if(!dset.same(e.source,e.target)){
			//MST.push_back(e);
			totalCost+=e.cost;
			dset.unite(e.source,e.target);
		}
	}
	return totalCost;
}


int main(){
int N,M,cost;
int source,target;
cin>>N>>M;
vector<Edge> edges;
for (int i = 0; i < M; ++i) {
	cin>>source>>target>>cost;
	edges.push_back(Edge(source,target,cost));
}
cout<<kruskal(N,edges)<<endl;
	return 0;
}

Measured memory_bytes: 5364
W, H, N = map(int, input().split())
lx, dy, rx, uy = 0, 0, W, H #最後に残る白の長方形
for i in range(N):
    x, y, a = map(int, input().split())
    if a == 1:
        if lx <= x:
            lx = x
    elif a == 2:
        if x <= rx:
            rx = x
    elif a == 3:
        if dy <= y:
            dy = y
    elif a == 4:
        if y <= uy:
            uy = y
if rx - lx <= 0 or uy - dy <= 0:
    print(0)
else:
    print((rx - lx) * (uy - dy))
        

Measured memory_bytes: 3060
#include <iostream>
#include <fstream>
#include <typeinfo>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<28;
const ll INF=1ll<<50;
const double pi=acos(-1);
const double eps=1e-10;
const ll mod=1e9+7;
const vi emp;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,-0};
const int DX[8]={-1,-1,-1,0,0,1,1,1},DY[8]={1,0,-1,1,-1,1,0,-1};

int A,B;
vi a,b;

vvi c(1001);

int func(int s,int n){
	auto i=upper_bound(c[n].begin(),c[n].end(),s);
	if(i==c[n].end()) return -1;
	return *i;
}

int main(){
	cin>>A>>B;
	a=vi(A);
	b=vi(B);
	for(int i=0;i<A;i++){
		cin>>a[i];
		c[a[i]].push_back(i);
	}
	for(int i=0;i<B;i++) cin>>b[i];
	int ans=0;
	for(int i=0;i<A;i++){
		int num=i,I=-1;
		while(num<B){
			int res=func(I,b[num]);
			if(res==-1) break;
			else I=res;
			num++;
		}
		ans=max(ans,num-i);
	}
	cout<<ans<<endl;
}

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

int main(void)
{
    int r, c, n;

    cin >> r >> c;
    vector<int> buffer(c);

    while (r--) {
        int sum_row = 0;
        for (int i = 0; i < c; i++) {
            cin >> n;
            sum_row += n;
            buffer[i] += n;
            cout << n << " ";
        }
        cout << sum_row << endl;
    }

    int sum = 0;
    for (int x: buffer) {
        sum += x;
        cout << x << " ";
    }
    cout << sum << endl;

    return 0;
}



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

int main()
{
	int n;
	long long a[110];
	
	scanf("%d", &n);
	a[0] = 2, a[1] = 1;
	for (int i = 2; i <= n; i++) {
		a[i] = a[i - 1] + a[i - 2];
	}
	printf("%lld\n", a[n]);
}


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

#if MYDEBUG
#include "lib/cp_debug.hpp"
#else
#define DBG(...) ;
#endif
#if __cplusplus <= 201402L
template <typename T>
T gcd(T a, T b) { return ((a % b == 0) ? b : gcd(b, a % b)); }
template <typename T>
T lcm(T a, T b) { return a / gcd(a, b) * b; }
#endif
using LL = long long;
constexpr LL LINF = 334ll << 53;
constexpr int INF = 15 << 26;
constexpr LL MOD = 1E9 + 7;

namespace Problem {
using namespace std;

class Solver {
 public:
  int n;
  vector<LL> a;
  vector<LL> rEven, r;
  //LazySegmentTree<Max_Set> rEven;
  Solver(LL n) : n(n), a(n), rEven(n + 1), r(n + 1){};

  void solve() {
    LL sum = 0;
    for (int i = 0; i < n; ++i) {
      cin >> a[i];
      sum += a[i];
    }
    LL ans = calc();
    reverse(a.begin(), a.end());
    ans = max(ans, calc());
    cout << sum - ans << endl;
  }
  LL calc() {
    //auto dp = [&](int x) -> auto & { return a[x + 1]; };
    for(int i=0; i<n+1; ++i){
      rEven[i] = 0;
      r[i] = 0;
    }
    
    for (int i = n - 1; i >= 0; --i) {
      LL tmp = rEven[i + 1];
      if (a[i] < 1) {
        tmp -= (2 - a[i]);
      } else {
        tmp += a[i] - (a[i] % 2);
      }
      rEven[i] = max(0ll, tmp);
    }
    DBG(rEven)
    for (int i = n - 1; i >= 0; --i) {
      LL tmp = r[i + 1];
      if (a[i] < 1) {
        tmp -= (1 - a[i]);
      } else {
        tmp += a[i] - ((a[i] + 1) % 2);
      }
      r[i] = max({0ll, tmp, rEven[i]});
    }//2222111122222
    DBG(r)
    for (int i = n - 1; i >= 0; --i) {
      LL tmp = r[i + 1];
      if (a[i] < 1) {
        tmp -= (2 - a[i]);
      } else {
        tmp += a[i] - (a[i] % 2);
      }
      r[i] = max({0ll, tmp, r[i]});
    }
    DBG(r)
    return *max_element(r.begin(), r.end());
  }
};

}  // namespace Problem

int main() {
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(false);
  // std::cout << std::fixed << std::setprecision(12);
  long long n = 0;
  std::cin >> n;

  Problem::Solver sol(n);
  sol.solve();
  return 0;
}


Measured memory_bytes: 4992
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <cmath>

#define AS(a) (sizeof(a)/sizeof(a[0]))
using namespace std;
long long int MOD = 1000000007;
long long int INF = 1000000007;

long long int gcd(long long int x, long long int y) {
    long long int r;
    while((r = x % y) != 0) {
        x = y;
        y = r;
    }
    return y;
}

long long int lcm(long long int x, long long int y){
  if(x / gcd(x,y) <= y / gcd(x,y)) {
    return x / gcd(x,y) * y;
  } else {
    return y / gcd(x,y) * x;
  }
}

int main() {
  int N;
  cin >> N;
  long long int T[N];
  for(int i = 0; i < N; i++) {
    cin >> T[i];
  }
  long long int ans = T[0];
  for(int i = 1; i < N; i++) {
    ans = lcm(T[i],ans);
  }
  cout << ans << endl;

}


Measured memory_bytes: 256
num = int(input())

put = []
stor = {}
i=0
while i<num :
    name = input()
    if name in stor.keys():
        stor[name] += 1
    else:
        stor[name] = 1
    i += 1

stor=sorted(stor.items(), key=lambda item:item[1], reverse=True)

m = stor[0][1]

for i in range(0,len(stor)):
    if stor[i][1]==m:
        put.append(stor[i][0])
    else:
        break
put.sort()

for i in put:
    print(i)

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

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

	for (int i = a; i <= b; i++)
	{
		string s = to_string(i);

		string s1 = "";
		for (int j = s.size() - 1; 0 <= j; j--)
		{
			s1 += s[j];
		}

		if (s == s1)
		{
			count++;
		}
	}

	cout << count << endl;
}


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

int main(){
    int n;
    cin >> n;
    vector<string>s(n);
    rep(i,n)cin >> s[i];
    bool ok = true;
    rep(i,n){
        if(i == 0)continue;
        int a = s[i-1].size()-1;
        if(s[i-1][a] != s[i][0])ok = false;
        rep(j,n){
            if(s[i] == s[j] && i != j)ok = false;
        }
    }
    if(ok)cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(void) {
	int a, b, c;
	cin >> a >> b >> c;
	if (a == b && b!=c || b == c && c!=a || c == a && a!=b) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
using namespace std;
int main(){
    int n,m,c,a[20][20],b[20],cnt=0,x;
    scanf("%d %d %d",&n,&m,&c);
    for(int i=0;i<m;i++){
        scanf("%d",&b[i]);
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            scanf("%d",&a[i][j]);
        }
    }
    for(int i=0;i<n;i++){
        x=0;
        for(int j=0;j<m;j++){
            x+=a[i][j]*b[j];
        }
        if(x+c>0){
            cnt++;
        }
    }
    printf("%d\n",cnt);
}

Measured memory_bytes: 128
// Problem : A - Nickname
// Contest : AtCoder - Tokio Marine & Nichido Fire Insurance Programming Contest 2020
// URL : https://atcoder.jp/contests/tokiomarine2020/tasks/tokiomarine2020_a
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

//mst,pq,mp,st,q
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define all(x) begin(x),end(x)

int mod = 1e9+7;
int inf = 4e18;
const int N = 5e5+5;
		
signed main()
{
    io
    int tt = 1;
    //cin>>tt;
    while(tt--)
    {
		string s;
		cin>>s;
		cout<<s.substr(0,3);		
    }
    return 0;
}


Measured memory_bytes: 3588
#include<iostream>
#include<map>
#include<algorithm>
#include<vector>
#include<stack>
#include<climits>
#include<cmath>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include<set>

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;

#define int long long
#define MOD (1000000007)
#define MINF (-1*(LLONG_MAX-10))
#define INF (LLONG_MAX-10)

namespace mp = boost::multiprecision;
// 任意長整数型
using Bint = mp::cpp_int;

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res%MOD;
}

// a^{-1} mod を計算する
long long modinv(long long a, long long mod) {
    return modpow(a, mod - 2, mod);
}

Bint gdb(Bint A,Bint B){
   return !B?A:gdb(B,A%B);
}
signed main(){
    int N;
    Bint A[10000];
    set<Bint> s;

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>N;
    for(int i=0;i<N;i++){
        cin>>A[i];
    }
    if(N==1){
        cout<<"1"<<endl;
        return 0;
    }
    Bint gd=A[0]*A[1]/gdb(A[0],A[1]);
    s.insert(A[0]);
    s.insert(A[1]);
    for(int i=2;i<N;i++){
        if(s.find(A[i])!=s.end()) continue;
        s.insert(A[i]);
        if(gd>A[i]) gd=gd*A[i]/gdb(gd,A[i]);
        else gd=gd*A[i]/gdb(A[i],gd);
    }

    int ans=0;
    int igd=(int)(gd%MOD);
    for(int i=0;i<N;i++){
        ans+=igd*modinv((int)A[i],MOD);
        ans%=MOD;
    }

    cout<<ans%MOD<<endl;
}


Measured memory_bytes: 1408
#include<bits/stdc++.h>                                                                                               
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 int long long
#define mk_p(a,b)   make_pair((a),(b))
using pii = pair<int,int>;
constexpr int INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;

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(0);
    ios::sync_with_stdio(false);
    int a,b,c,d,e,k;
    cin >> a >> b >> c >> d >> e >> k;
    if(e - a > k) cout << ":(\n";
    else cout << "Yay!\n";
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
int N, M;
int Ai[50];
int Bi[50];
int tree[51];

int parent(int n) {
    if (tree[n] == n) {
        return n;
    }
    int p = parent(tree[n]);
    return tree[n] = p;
}
//i番目が橋かどうかチェック
bool isBridge(int idx) {
    //idx番目を除去したときに島が独立になるか調べる
    rep(i, N) tree[i] = i;

    rep(i, M) {
        if (i == idx) {
            continue;
        }
        int a = parent(Ai[i]);
        int b = parent(Bi[i]);
        if (a == b) {
            continue;
        }
        tree[b] = a;
    }
    //全部が同一グループにある＝橋でない
    int p0 = parent(0);
    rep (i, N) {
        if (parent(i) != p0) {
            return true;
        }
    }
    return false;
}


int main()
{
    cin >> N >> M;
    rep(i, M) {
        int a, b;
        cin >> a >> b;
        Ai[i] = a - 1;
        Bi[i] = b - 1;
    }
    int count = 0;
    rep (i, M) {
        if (isBridge(i)) {
            count++;
        }
    }
    cout << count << endl;
    return 0;
}


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

int main() {
  	int n;
	string st, en;
 	cin >> n >> st >> en;
  	int ans = 2 * n;
	for (int i = 1; i <= n; i++) 
    	if(st.substr(n - i, i) == en.substr(0, i))
  			ans = 2 * n - i;
  	cout << ans << endl;
  	return 0;
}

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

int main(){
    string s;
    cin >> s;
    for(int i = 1;i < 4;++i){
        if(s[i-1] == s[i]){
            cout << "Bad" << endl;
            return 0;
        }
    }
    cout << "Good" << endl;
    return 0;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]

graph = [[False] * N for _ in range(N)]
for a, b in X:
    graph[a - 1][b - 1] = True
    graph[b - 1][a - 1] = True


def dfs(u):
    visited[u] = True
    for v in range(N):
        if visited[v] or not graph[u][v]:
            continue
        dfs(v)


res = 0
for i in range(M):
    a, b = X[i]
    a -= 1
    b -= 1
    
    graph[a][b] = False
    graph[b][a] = False
    
    visited = [False] * N
    dfs(0)
    res += int(not all(visited))
    
    graph[a][b] = True
    graph[b][a] = True
    
print(res)


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

int main(){
	long long t,n,sum=0;
	while(cin>>t>>n){
		sum=0;
		if(t==1)sum+=6000*n;
		else if(t==2)sum+=4000*n;
		else if(t==3)sum+=3000*n;
		else if(t==4)sum+=2000*n;
		cout<<sum<<endl;
	}
	return 0;
}

Measured memory_bytes: 1156