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

using ll = long long;
#define int long long

// [a -> b-1]
#define reps(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
// [0 -> a-1]
#define rep(i, a) reps(i, 0, (a))
// [a-1 -> b]
#define rreps(i, a, b) for (int i = (int)((a)-1); i >= (int)(b); i--)
// [a-1 -> 0]
#define rrep(i, a) rreps(i, a, 0)
#define all(v) (v).begin(), (v).end()
// next_permutation(all(v))
#define PERM(v) next_permutation(all(v))
/*sort(all(v));
 * (v).erase(unique(all(v)), v.end())*/
#define UNIQUE(v)\
	sort(all(v));\
	(v).erase(unique(all(v)), v.end())
#define MINV(v) min_element(all(v))
#define MAXV(v) max_element(all(v))
#define MIN3(a, b, c) min(min(a, b), c)
#define MIN4(a, b, c, d) min(MIN3(a, b, c), d)
#define MIN5(a, b, c, d, e) min(MIN4(a, b, c, d), e)
#define MIN6(a, b, c, d, e, f) min(MIN5(a, b, c, d, e), f)
#define MAX3(a, b, c) max(max(a, b), c)
#define MAX4(a, b, c, d) max(MAX3(a, b, c), d)
#define MAX5(a, b, c, d, e) max(MAX4(a, b, c, d), e)
#define MAX6(a, b, c, d, e, f) max(MAX5(a, b, c, d, e), f)
// b is [a, c)
#define RANGE(a, b, c) ((a) <= (b) && (b) < (c))
// c is [a, e) && d is [b, f)
#define RANGE2D(a, b, c, d, e, f) (RANGE((a), (c), (e)) && RANGE((b), (d), (f)))
#define chmin(a, b) a = min(a, (b))
#define chmin3(a, b, c) a = MIN3(a, (b), (c))
#define chmin4(a, b, c, d) a = MIN4(a, (b), (c), (d))
#define chmin5(a, b, c, d, e) a = MIN5(a, (b), (c), (d), (e))
#define chmin6(a, b, c, d, e, f) a = MIN6(a, (b), (c), (d), (e), (f))
#define chmax(a, b) a = max(a, (b))
#define chmax3(a, b, c) a = MAX3(a, (b), (c))
#define chmax4(a, b, c, d) a = MAX4(a, (b), (c), (d))
#define chmax5(a, b, c, d, e) a = MAX5(a, (b), (c), (d), (e))
#define chmax6(a, b, c, d, e, f) a = MAX6(a, (b), (c), (d), (e), (f))
#define fcout cout << fixed << setprecision(15)
#define YES(f) cout << ((f) ? YES_STR : NO_STR) << endl;

using namespace std;

int solve(int x, int y, int s) {
	int res = 0;
	reps(i, 1, s-1) {
		reps(j, 1, s-1) {
			int X = i * (100 + x) / 100;
			int Y = j * (100 + x) / 100;
			if (X + Y > s) break;
			if (X + Y < s) continue;
			chmax(res, i * (100 + y) / 100 + j * (100 + y) / 100);
		}
	}
	return res;
}

signed main() {
	int x, y, s;
	while (cin >> x >> y >> s, x) cout << solve(x, y, s) << endl;
}




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

const ll MX = 1e18;

int main() {
  int n;
  cin >> n;
  ll ans = 1;
  bool ng = false;
  rep(i,n) {
    ll a;
    cin >> a;
    if (a == 0) {
      cout << 0 << endl;
      return 0;
    }
    if (ng || MX/ans < a) {
      ng = true;
    }
    ans *= a;
  }
  if (ng) cout << -1 << endl;
  else cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3648
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000009;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-4;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
struct edge { int to, len, cost; };
vector<edge> G[1 << 14];
void init(int n) {
	rep(i, n) {
		G[i].clear();
	}
}
struct vertice {
	int id, dis;
	bool operator<(const vertice &v)const {
		if (v.dis != dis)return v.dis < dis;
		return v.id < id;
	}
};
int main(){
	int n, m;
	while (cin >> n >> m, n) {
		init(n);
		rep(i, m) {
			int u, v, d, c; cin >> u >> v >> d >> c; u--; v--;
			G[u].push_back({ v,d,c });
			G[v].push_back({ u,d,c });
		}
		int d[1 << 14];
		fill(d, d + n, mod);
		d[0] = 0;
		priority_queue<vertice> q; q.push({ 0,0 });
		while (!q.empty()) {
			vertice v = q.top(); q.pop();
			rep(i, (int)G[v.id].size()) {
				int to = G[v.id][i].to;
				int nd = v.dis + G[v.id][i].len;
				if (nd < d[to]) {
					d[to] = nd; q.push({ to,d[to] });
				}
			}
		}
		int out = 0;
		rep1(i, n - 1) {
			int mi = mod;
			rep(j, G[i].size()) {
				int to = G[i][j].to;
				if (d[to] + G[i][j].len == d[i]) {
					mi = min(mi, G[i][j].cost);
				}
			}
			out += mi;
		}
		cout << out << endl;
	}
	return 0;
}


Measured memory_bytes: 5268
#pragma region include
#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <bitset>

#include <queue>
#include <complex>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <fstream>
#include <random>
//#include <time.h>
#include <ctime>
#pragma endregion //#include
/////////
#define REP(i, x, n) for(int i = x; i < n; ++i)
#define rep(i,n) REP(i,0,n)
/////////
#pragma region typedef
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
#pragma endregion //typedef
////定数
const int INF = (int)1e9;
const LL MOD = (LL)1e9+7;
const LL LINF = (LL)1e18;
const double PI = acos(-1.0);
const double EPS = 1e-9;
/////////
using namespace::std;

void solve(){
	int N;
	LL X;
	cin >> N >> X;
	vector<LL> A(N);
	for(int i=0;i<N;++i){
		cin >> A[i];
	}
	LL ans = 0;
	for(int i=1;i<N;++i){
		LL temp = A[i-1] + A[i];
		if( temp > X ){
			LL sub = temp-X;//減らす数
			if( A[i] >= sub ){
				A[i] -= sub;
				ans += sub;
			}else{
				sub -= A[i];
				ans += A[i];
				A[i] = 0;
				A[i-1] -= sub;
				ans += sub;
			}
		}
	}
	cout << ans << endl;
}

#pragma region main
signed main(void){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	
	
	solve();
}
#pragma endregion //main()


Measured memory_bytes: 1024
//clear adj and visited vector declared globally after each test case
//check for long long overflow
//while adding and subs check if mod becomes -ve
//while using an integer directly in a builtin function add ll
//Mod wale question mein last mein if dalo ie. Ans<0 then ans+=mod;
//Dont keep array name as size or any other key word

#include <bits/stdc++.h> 
#include <ext/pb_ds/assoc_container.hpp>
//#define int long long
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);cout.precision(dbl::max_digits10);
#define pb push_back
#define mod 1000000007 //998244353
#define lld long double
#define mii map<int, int>
#define mci map<char, int>
#define msi map<string, int>
#define pii pair<int, int>
#define ff first
#define ss second 
#define all(x) (x).begin(), (x).end()
#define rep(i,x,y) for(int i=x; i<y; i++)    
#define fill(a,b) memset(a, b, sizeof(a))
#define vi vector<int>
#define setbits(x) __builtin_popcountll(x)
#define print2d(dp,n,m) for(int i=0;i<=n;i++){for(int j=0;j<=m;j++)cout<<dp[i][j]<<" ";cout<<"\n";}
typedef std::numeric_limits< double > dbl;
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
const long long N=200005, INF=2000000000000000000;
lld pi=3.1415926535897932;
int lcm(int a, int b)
{
    int g=__gcd(a, b);
    return a/g*b;
}
int power(int a, int b, int p)
    {
        if(a==0)
        return 0;
        int res=1;
        a%=p;
        while(b>0)
        {
            if(b&1)
            res=(res*a)%p;
            b>>=1;
            a=(a*a)%p;
        }
        return res;
    }

int32_t main()
{
    IOS;
    int a,b;
    cin>>a>>b;
    for(int i=1;;i++)
    {
        int x1=(i*8)/100;
        int x2=i/10;
        if(x1>a||x2>b)
        break;
        if(x1==a&&x2==b)
        {
            cout<<i;
            return 0;
        }
    }
    cout<<-1;
}

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

int main(){
  long long A,B,C,K;
  cin>>A>>B>>C>>K;

  if(K<=A){
    cout << K << endl;
    return 0;
  }
  if(K<=A+B){
    cout << A << endl;
    return 0;
  }
  cout << A - (K-A-B);
  return 0;
}

Measured memory_bytes: 3672
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
	char s[102];
	char t[102];
	int ps=0;
	int ps2;
	int le;
	bool flag;
	scanf("%s%s",&s,&t);
	for(ps2=0;s[ps2]!='\0';ps2++);
	le=ps2;
	for(int i=0;i<le;i++)
	{
		flag=true;
		for(int j=0;j<le;j++)
			if(t[j]!=s[ps+j])
			{
				flag=false;
				break;
			}
		if(flag)
		{
			printf("Yes");
			return 0;
		}
		s[ps2]=s[ps];
		ps++;
		ps2++;
	}
	printf("No");
	return 0;
}
/*
aaaaaaaaaaaaaaab
aaaaaaaaaabaaaaa
*/

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>

int main() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++)
    {
        std::cin >> a[i];
    }

    std::vector<long long> sum(n + 1);
    sum[0] = 0;
    for (int i = 0; i < n; i++)
    {
        sum[i + 1] += a[i] + sum[i];
    }

    long long ans = __LONG_LONG_MAX__;
    for (int i = 1; i < n; i++)
    {
        long long x = sum[i];
        long long y = sum[n] - sum[i];
        long long min = std::abs(x - y);
        ans = std::min(ans, min);
    }

    std::cout << ans << "\n";
}

Measured memory_bytes: 5620
// finish date: 2018/07/07
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int (i)=a;(i)<(b);(i)++)
#define rep(i, n)  FOR(i,0,n)
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>>
        vvvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<double> vd;
typedef vector<vector<double>> vvd;
typedef vector<vector<vector<double>>>
        vvvd;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef pair<int, int> pii;
const int bigmod = 1000000007;
const int INF = 1050000000;


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

    //2個あるやつ
    int com = max(0, n - d * 2);

    //１こあるやつ
    int semi = d * 2;
    double ans = (double) (m - 1) * (2 * com + semi) / pow(n, 2);
    if (d == 0) ans /= 2;
    printf("%.7f\n", ans);


    return 0;
}



Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
       
        Scanner sc = new Scanner(System.in);
        int sanka = sc.nextInt();
        int point = sc.nextInt();
        int seikai = sc.nextInt();
        int[] array = new int[sanka];

        for(int i = 0; i < sanka; i++){
            array[i] = point - seikai;
        }
        for(int i = 0; i < seikai; i++){
            array[sc.nextInt() - 1]++;
        }
        for(int i = 0; i < sanka; i++){
            if(array[i] <= 0){
                System.out.println("No");
            }else{
                System.out.println("Yes");
            }
        }
    }     
}

Measured memory_bytes: 70688
import re
S = input()
N1 = S.replace('A','0').replace('BC','1')
S_li = re.split('B|C',N1)
 
count = 0
for l in S_li:
    a = sum([i for i,x in enumerate(l) if '1' in x])
    su=sum([x for x in range(l.count('1'))])
    count += (a-su)
print(str(count))

Measured memory_bytes: 59516
card=[]

for i in range(3):
    a,b,c= map(int,input().split())
    card.append(a)
    card.append(b)
    card.append(c)

N = int(input())

for i in range(N):
    b=int(input())
    if b in card:
        num=card.index(b)
        card[num]=0

r1=card[0]+card[1]+card[2]
r2=card[3]+card[4]+card[5]
r3=card[6]+card[7]+card[8]

l1=card[0]+card[3]+card[6]
l2=card[1]+card[4]+card[7]
l3=card[2]+card[5]+card[8]

m1=card[0]+card[4]+card[8]
m2=card[2]+card[4]+card[6]

if r1==0:
    print("Yes")
elif r2==0:
    print("Yes")
elif r3==0:
    print("Yes")
elif l1==0:
    print("Yes")
elif l2==0:
    print("Yes")
elif l3==0:
    print("Yes")
elif m1==0:
    print("Yes")
elif m2==0:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <cmath>
#include <algorithm>
#include <unordered_set>
using namespace std;

struct segment_tree {
  int NV;
  vector<int> dat;
  segment_tree(int N) {
    NV = 1;
    while (NV < N) NV = NV << 1;
    dat.resize(NV*2 -1);
    //cout << "sg init: NV = " << NV << endl; 
    for (int i = 0; i < NV; i++) {
      dat[i+NV-1] = 0;
    }
    for (int i = NV - 2; i >=0; i--) {
      dat[i] = max(dat[i*2+1], dat[i*2+2]);
    }
  }
  void update(int idx, int val) {
    //cout << "update called: " << idx << "," << val << endl;
    if (idx < 0) return;
    idx += NV - 1;
    dat[idx] = val;
    //cout << idx << ":" << dat[idx].first << "," << dat[idx].second << endl;
    while (idx > 0) {
      idx = (idx - 1) / 2;
      dat[idx] = max(dat[idx*2+1], dat[idx*2+2]);
    }
    return;
  }
  int query(int a, int b) {
    return _query(a, b, 0, 0, NV);
  }
  int _query(int a, int b, int k, int l, int r) {
    //cout << "query called :" << a << "," << b << "," << k << "," << l << "," << r << endl;
    if (r <= a || b <= l) return 0;
    if (a <= l && r <= b) return dat[k];
    else {
      int vl = _query(a, b, k*2 + 1, l, (l + r) / 2);
      int vr = _query(a, b, k*2 + 2, (l + r) / 2, r);
      //cout << "querry return val: " << min(vr,vl).first << "," << min(vr,vl).second << endl;
      return max(vl, vr);
    }
  }
};

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

  int32_t N, K;
  cin >> N >> K; 
  segment_tree st(300001);
  int res = 0;
  for (int i = 0; i < N; i++) {
    int a;
    cin >> a;
    int plen = st.query(max(0, a - K), a + K + 1);
    //cout << i << "," << plen << endl;
    res = max(res, plen + 1);
    st.update(a, plen + 1);
  }
  cout << res << endl;
  
  return 0;
}



Measured memory_bytes: 7428
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < n;i ++ )
#define ll long long

using namespace std;
typedef pair<int, int> P;
// input


int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	
    char abcd[4];
    cin >> abcd;
    vector<int> numstr(4);
    rep(i,4)numstr[i] = abcd[i];

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

    if(numstr[0] == numstr[1] && numstr[2] == numstr[3] && numstr[0] != numstr[3]) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define forE(i,x) for(int i=head[x];i!=-1;i=ne[i])
using namespace std;
typedef long long i64;
typedef unsigned long long u64;
typedef unsigned u32;
typedef pair<int,int> pin;
#define mk(a,b) make_pair(a,b)
#define lowbit(x) ((x)&(-(x)))
#define sqr(a) ((a)*(a))
#define clr(a) (memset((a),0,sizeof(a)))
#define ls ((x)<<1)
#define rs (((x)<<1)|1)
#define mid (((l)+(r))>>1)
#define pb push_back
#define w1 first
#define w2 second
inline void read(int &x){
	x=0;int f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
inline void judge(){
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
}
/*******************************head*******************************/
typedef long double ld;
ld solve(int n,ld a,ld d){
	if(!n)return 0;
	ld res=a+d*(2*n-1)/2;
	return res+solve(n-1,(a*(n-1)*2+(a+2*d)+(3*a+3*d))/(2*n),((a+d)*(2*(n-1)-1)+(a+3*d)*2+(3*a+6*d))/(2*n)-(a*(n-1)*2+(a+2*d)+(3*a+3*d))/(2*n));
}
int main(){
	int n;double a,b;
	read(n);scanf("%lf %lf",&a,&b);
	printf("%.10Lf\n",solve(n,a,b));
	return 0;
}


Measured memory_bytes: 15872
def test():
    n = list(input())
    a = int(n[0]+n[1])
    b = int(n[2]+n[3])
    if a > 12 or a == 0:
        if b == 0 or b > 12:
            print("NA")
        else:
            print("YYMM")
    elif a <= 12:
        if b <= 12 and b != 0:
            print("AMBIGUOUS")
        elif b > 12 or b == 0:
            print("MMYY")


if __name__ == "__main__":
    test()


Measured memory_bytes: 3060
#include<cstdlib>
#include<cmath>
#include<iomanip>
#include<iostream>

using namespace std;

int main(){
    int a,b,h,m;
    double ang,rad,ans;
    static const double pi = 3.141592653589793;
    
    cin>>a>>b>>h>>m;
    
    ang=30*h+0.5*m-6*m;
    
    if(ang==0){
        ans=abs(b-a);
        cout<<fixed<<setprecision(10)<<ans<<endl;
    }else if(ang==180 || ang==-180){
        ans=a+b;
        cout<<fixed<<setprecision(10)<<ans<<endl;
    }else{
        rad=ang*pi/180;
        ans=pow(a,2.0)+pow(b,2.0)-2.0*a*b*cos(rad);
        cout<<fixed<<setprecision(10)<<sqrt(ans)<<endl;
    }
}

Measured memory_bytes: 4148
#include <math.h>

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

int calc(int A, int B, int C) { return abs(A - B) + abs(B - C); }

int main() {
  int A, B, C;
  cin >> A >> B >> C;

  int ret = calc(A, B, C);
  ret = min(ret, calc(A, C, B));
  ret = min(ret, calc(B, A, C));
  ret = min(ret, calc(B, C, A));
  ret = min(ret, calc(C, A, B));
  ret = min(ret, calc(C, B, A));
  cout << ret << endl;

  return 0;
}


Measured memory_bytes: 256
fn main() {
 fn read<T: std::str::FromStr>() -> T {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).ok();
        s.trim().parse().ok().unwrap()
    }
    fn read_vec<T: std::str::FromStr>() -> Vec<T> {
        read::<String>().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
    }
    fn main() {
        let HW = read_vec::<i32>();
        let hw = read_vec::<i32>();
        println!("{}", (HW[0]-hw[0])*(HW[1]-hw[1]));
    }
    main()
}

fn answer(HW:Vec<i32>, hw:Vec<i32>) {
    println!("{}", (HW[0]-hw[0])*(HW[1]-hw[1]));
}


Measured memory_bytes: 4352
import math
a,b,x=map(int,input().split())

if x<=a**2*b/2:
 c=2*x/a/b
 e=c/((b**2+c**2)**(0.5))
 d=math.acos(e)*180/math.pi
else:
 c=2*b-(2*x/a/a)
 e=c/((a**2+c**2)**(0.5))
 d=90-math.acos(e)*180/math.pi
print(d)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define fi first
#define se second
#define mp make_pair
#define itrfor(itr,A) for(auto itr = A.begin(); itr !=A.end();itr++)
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
typedef long long llong;
char moji[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char moji2[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char moji3[10]={'0','1','2','3','4','5','6','7','8','9'};
#define Sort(a) sort(a.begin(),a.end());
#define Reverse(a) reverse(a.begin(),a.end());
#define print(a) cout << a << endl;
#define MOD llong(1e9+7)
#define MAX int(2 * 1e5 +5)
#define debug(x)  cout << #x << " = " << (x) << endl;
#define pi acos(-1.0)
#define int llong
#define INF llong(1e18 + 3)
template<class T> bool chmax(T &a,  T b) {if(a<b){a=b; return 1;} return 0;}
template<class T> bool chmin(T &a,  T b) {if(a>b){a=b; return 1;} return 0;}
bool Add(int &a,int b){a = (a + b) % MOD;}
void myprint(int* A,int A_num){
   REP(i,A_num) cout << A[i] << " ";
   cout << endl;
}

bool comp(pair<int,int> x, pair<int,int> y){
    if(x.fi != y.fi) return x.fi < y.fi;
    else return x.se > y.se;
}


signed main(){
    int n;
    int ans = 0;
    cin >> n;
    pair<int,int> A[n];
    REP(i,n){
        cin >> A[i].fi >> A[i].se;
        A[i].se += 1;
        chmax(ans,A[i].se - A[i].fi);

    }
    sort(A,A+n,comp);
    pair<int,int> B[n];
    B[0] = A[0];
    int cnt = 1;
    bool migi,hidari;
    migi = false;
    hidari =  false;
    FOR(i,1,n){
        while(cnt >= 1 and B[cnt - 1].se >= A[i].se){
            cnt --;
        }
        B[cnt] = A[i];
        cnt ++;

    }
    /*
    cout << endl;
    REP(i,cnt){
        cout << B[i].fi << " " << B[i].se << endl;
    }
    */
    if(cnt == 1){
        cout << ans + B[0].se - B[0].fi << endl;
        return 0;
    }
    

     

     REP(i,cnt- 1){
         chmax(ans, max(llong(0),(B[0].se - B[i].fi)) + max(llong(0),(B[i+1].se - B[cnt-1].fi)) );
     }
     if(cnt != 1){
     REP(i,n){
         if(A[i].fi == B[0].fi and A[i].se == B[0].se){
             if(hidari == false){
             chmax(ans,A[i].se - A[i].fi  + max(llong(0),B[1].se - B[cnt - 1].fi) );
             }
             else{
             chmax(ans,A[i].se - A[i].fi  + max(llong(0),B[0].se - B[cnt - 1].fi) );                 
             }
         }
         else if(A[i].fi == B[cnt-1].fi and A[i].se == B[cnt - 1].se){
             chmax(ans,A[i].se - A[i].fi + max(llong(0),B[0].se -B[cnt - 2].fi ));
         }
         else chmax(ans,A[i].se - A[i].fi + max(llong(0),B[0].se -B[cnt - 1].fi ));
     }
     }
     cout << ans << endl;


}

Measured memory_bytes: 3328
#include <stdio.h>
int main(void) {
	int r, c;
	int i, j;
	int gr[101][101] = { 0 };

	scanf("%d %d", &r, &c);

	for (i = 0; i < r; i++) {
		for (j = 0; j < c; j++) {
			scanf("%d", &gr[i][j]);
		}
	}

	for (i = 0; i < r; i++) {
		for (j = 0; j < c; j++) {
			gr[r][j] += gr[i][j];
			gr[i][c] += gr[i][j];
			gr[r][c] += gr[i][j];
		}
	}

	for (i = 0; i <= r; i++) {
		for (j = 0; j < c; j++) {
			printf("%d ", gr[i][j]);
		}
		printf("%d\n",gr[i][c]);
	}
	return 0;
}

Measured memory_bytes: 648
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif


using namespace std;

// #define int long long
struct Fast {Fast(){std::cin.tie(0);ios::sync_with_stdio(false);}} fast;

inline bool inside(int y, int x, int H, int W) {return y >= 0 && x >= 0 && y < H && x < W;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

const int MOD = 1e9 + 7;
const int INF = INT_MAX;

signed main() {
    Fast();

    string s1, s2, s3;
    cin >> s1 >> s2 >> s3;
    cout << s1[0] << s2[1] << s3[2] << endl;

    return 0;
}



Measured memory_bytes: 256
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools, bisect
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def S(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007


class FactInv:
    def __init__(self, N, MOD=1000000007):
        fact = [1]*(N+1)
        for i in range(1, N+1):
            fact[i] = fact[i - 1] * i % MOD

        inv = [None]*(N+1)
        inv[N] = pow(fact[N], MOD - 2, MOD)

        for i in range(N)[::-1]:
            inv[i] = inv[i + 1] * (i + 1) % MOD

        self.N = N
        self.MOD = MOD
        self.fact = fact
        self.inv = inv

    def perm(self, a, b):
        if a > self.N or b > self.N:
            raise ValueError(
                "\nPermutaion arguments are bigger than N\n N = {}, a = {}, b = {}".format(self.N, a, b))
        return self.fact[a] * self.inv[a-b] % self.MOD

    def comb(self, a, b):
        if a > self.N or b > self.N:
            raise ValueError(
                "\nCombination arguments are bigger than N\n N = {}, a = {}, b = {}".format(self.N, a, b))
        return self.fact[a] * self.inv[b] * self.inv[a-b] % self.MOD


def main():
    N, M = LI()
    factinv = FactInv(M)

    a = factinv.perm(M, N)

    tmp = a
    for k in range(1, N + 1):
        tmp = (tmp + factinv.comb(N, k) * factinv.perm(M - k, N - k) * pow(-1, k)) % MOD

    print(a * tmp % MOD)





if __name__ == '__main__':
    main()

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


int main(){
    string s="ACL";
    int n;
    cin>>n;
    rep(i,n) cout<<s;
    return 0;
}

Measured memory_bytes: 3620
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Objects;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author dyominov
 */
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);
        BBiteEating solver = new BBiteEating();
        solver.solve(1, in, out);
        out.close();
    }

    static class BBiteEating {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            int l = in.nextInt();
            Apple[] apples = new Apple[n];
            for (int i = 0; i < n; i++) {
                apples[i] = new Apple(l + i);
            }
            int sumMax = 0;
            for (int i = 0; i < n; i++) {
                sumMax += apples[i].flavor;
            }
            int res = 0;
            int abs = Integer.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                if (Math.abs(sumMax - (sumMax - apples[i].flavor)) < abs) {
                    abs = Math.abs(sumMax - (sumMax - apples[i].flavor));
                    res = i;
                }
            }
            out.print(sumMax - apples[res].flavor);
        }

        class Apple implements Comparable<Apple> {
            int flavor;

            public Apple(int flavor) {
                this.flavor = flavor;
            }

            public boolean equals(Object o) {
                if (this == o) return true;
                if (o == null || getClass() != o.getClass()) return false;
                Apple apple = (Apple) o;
                return flavor == apple.flavor;
            }

            public int hashCode() {
                return Objects.hash(flavor);
            }

            public int compareTo(Apple o) {
                return this.flavor - o.flavor;
            }

        }

    }

    static class InputReader implements AutoCloseable {
        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());
        }

        public void close() {
        }

    }
}



Measured memory_bytes: 23252
class Solver(object):
    def __init__(self):
        self.a, self.b = list(map(int, input().split(" ")))

    def solve(self):
        last = self.b - self.a
        right_height = sum(range(1, last+1))
        snow_height = right_height - self.b
        print(snow_height)


if __name__ == "__main__":
    s = Solver()
    s.solve()

Measured memory_bytes: 2940
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
#define MOD (1000000007l)
#define rep(i, n) for(long i = 0; i < n; i++)

using namespace std;

vector<long> input_array(long N) { vector<long> ret(N); for (long i = 0; i < N; i++) cin >> ret[i]; return ret; }

vector<long> foo(const vector<long> &arg) {
  auto ret = arg;
  for (long i = arg.size() - 2; i >= 0; i--) {
    ret[i] += ret[i+1];
  }
  return ret;
}

void solve() {
  long N;
  cin >> N;
  auto A = input_array(N);
  auto B = input_array(N);
  auto C = input_array(N);
  sort(A.begin(), A.end());
  sort(B.begin(), B.end());
  sort(C.begin(), C.end());
  vector<long> bbb(N, 0);
  rep (i, N) bbb[i] = C.end() - upper_bound(C.begin(), C.end(), B[i]);
  bbb = foo(bbb);
  vector<long> aaa(N, 0);
  rep (i, N) {
    long tmp = upper_bound(B.begin(), B.end(), A[i]) - B.begin();;
    if (tmp == N) continue;
    aaa[i] = bbb[tmp];
  }
  aaa = foo(aaa);
  cout << aaa[0] << endl;
}

int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout.precision(12);
  solve();
  return 0;
}


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

int main(void) {
    int N;
    cin >> N;
    vector<long> H(N);

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

    int cnt = 0;
    int ans = 0;

    for (int i = N - 1; i > 0; i--) {
        if (H[i - 1] - H[i] >= 0)
            cnt++;
        else {
            ans = max(ans, cnt);
            cnt = 0;
        }
    }
    ans = max(ans, cnt); // 追記箇所(for文の最後で、if (H[i - 1] - H[i] >= 0)が実行されるとansが更新されないので、for文抜けてから更新)

    cout << ans << endl;
}


Measured memory_bytes: 1024
class UnionFind():
    def __init__(self, n):
        self.parent = [-1 for _ in range(n)]
        # 正==子: 根の頂点番号 / 負==根: 連結頂点数

    def find(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        else:
            if self.size(x) < self.size(y):
                x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        x = self.find(x)
        return -self.parent[x]

    def is_root(self, x):
        return self.parent[x] < 0


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

uf = UnionFind(n)

for _ in range(m):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    uf.unite(x, y)

print(sum(uf.is_root(i) for i in range(n)))


Measured memory_bytes: 5488
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i,n) for(int i=0; i < (n); ++i)
#define REPR(i,n) for(int i=(n); i >=0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
 
typedef long long ll;
#define INF 1e9
 
int main(){
  int N, K;
  cin >> N >> K;
  vector<int> p(2* 1e5+9, 0);
  FOR(i, 1, N+1){
    if(i < K){
      ll me = i;
      while(me < K){
        me*=2;
        p[i]++;
      }
    }
  }
 
  double ans=0;
  FOR(i, 1, N+1){
    double me = 1;
    REP(j, p[i]){
      me *=2;
    }
    ans += 1 / me;
  }
  ans /= N;
  printf("%.12lf\n", ans);
  
  return 0;
}

Measured memory_bytes: 1024
x, y = map(int,input().split())

if x == y == 2:
    print("Yes")
elif x in [4, 6, 9, 11] and y in [4, 6, 9, 11]:
    print("Yes")
elif x in [1, 3, 5, 7, 8, 10, 12] and y in [1, 3, 5, 7, 8, 10, 12]:
    print("Yes")
else: 
    print("No")

Measured memory_bytes: 3060
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author aajisaka
 */

#include<bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SPEED ios_base::sync_with_stdio(false);cin.tie(nullptr)
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

using ll = long long;
using P = pair<ll, ll>;

constexpr double PI = 3.14159265358979323846;
mt19937_64 engine(chrono::steady_clock::now().time_since_epoch().count());

class EGetEverything {
public:
    void solve(istream& cin, ostream& cout) {
      SPEED;
      int n; cin >> n;
      int s = 1<<n;
      vector<int> dp(s, INT_MAX/2);
      dp[0] = 0;

      int m; cin >> m;
      vector<pair<int, int>> vec(m);
      rep(i, m) {
        int a, b; cin >> a >> b;
        vec[i].first = a;
        rep(j, b) {
          int c; cin >> c;
          c--;
          vec[i].second += (1<<c);
        }
      }

      rep(i, s) {
        rep(j, m) {
          chmin(dp[i|vec[j].second], dp[i] + vec[j].first);
        }
      }

      if (dp[s-1] == INT_MAX/2) {
        cout << -1 << endl;
      } else {
        cout << dp[s-1] << endl;
      }

    }
};

signed main() {
  EGetEverything solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}

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

// 総数を1000000007（素数）で割った余り
const long long mod = 1e9 + 7;

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

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

int main(){
    int n;
    cin >> n;
    vpii a(n);
    rep(i, n) {
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(rall(a));
    vector<vll> dp(n+1, vll(n+1, -1));
    rep(i, n+1) rep(j, n+1-i) {
        if (i==0 && j==0) {
            dp[i][j] = 0;
            continue;
        }
        int na = a[i+j-1].first, np = a[i+j-1].second;
        ll u = (i>0)?dp[i-1][j]:0, l = (j>0)?dp[i][j-1]:0;
        if (i>0) u += ll(na) * abs(np-(n-i));
        if (j>0) l += ll(na) * abs(np-(j-1));
        dp[i][j] = max(u, l);
    }
    ll ans = 0;
    rep(i, n+1) ans = max(ans, dp[i][n-i]);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 34636
/*
Why don't I solve this before E :P SIGH
*/
#include<bits/stdc++.h>
using namespace std;
int n,k,x;

int main(){
    scanf("%d",&k);
    n=(1<<k);
    multiset<int> ms;
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        ms.insert(x);
    }
    vector<int> a={*prev(ms.end())};
    ms.erase(ms.find(a[0]));
    while(k--){
        n=(int)a.size();
        for(int i=0;i<n;i++){
            if(*ms.begin()>=a[i]){
                return !printf("No\n");
            }
            auto it = ms.lower_bound(a[i]);
            --it;
            a.push_back(*it);
            ms.erase(it);
        }
    }
    printf("Yes\n");
}


Measured memory_bytes: 13692
from queue import Queue 
K=int(input())

q=Queue()

for i in range(1,min(9,K)+1):
    q.put(i)

for k in range(K):
    a=q.get()
    #print(a)
    if k!=K-1:
        b=a%10
        for j in range(max(0,b-1),min(9,b+1)+1):
            q.put(int(str(a)+str(j)))
    else:
        print(a)

Measured memory_bytes: 11480
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int l, r, d, count=0;
  cin >> l >> r >> d;
  while(l <= r) {
    if(l % d == 0) {
      count++;
    } 
    l++;
  }
  cout << count << '\n';
}

Measured memory_bytes: 3620
#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <iomanip>
#include <queue>


using namespace std;


int main() {

	int N, a, count = 1, sum = 0;

	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> a;
		if (count == a) {
			count++;
		}
		else {
			sum++;
		}
	}
	
	if (N == count + sum - 1 && sum != N) {
		cout << sum;
	}
	else {
		cout << "-1";
	}
	
	return 0;
}


Measured memory_bytes: 256
/*-------------------------------"ANJAN AGARWALA"-----------------------------

         _/_/_/_/    _/_/    _/   _/_/_/_/   _/_/_/_/    _/_/    _/   
        _/    _/    _/ _/   _/         _/   _/    _/    _/ _/   _/        
       _/_/_/_/    _/   _/ _/         _/   _/_/_/_/    _/  _/  _/         
      _/    _/    _/    _/_/   _/    _/   _/    _/    _/    _/_/  
     _/    _/    _/      _/   _/_/_/_/   _/    _/    _/      _/   

-------------------------------------@anjn98---------------------------------*/

//#define opti
#ifdef opti
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#endif

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

typedef long long int ll;
typedef long long int LL;
typedef unsigned long long int ull;
ll power(ll x,ll y,ll p){ll r=1; x=x%p; while(y){ if(y&1) r= r*x%p; y=y>>1; x=x*x%p; } return r; }
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;*/

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int csrand(int l=0, int r=1e9){
    uniform_int_distribution<int> uid(l, r);
    return uid(rng);
}

#define IO              ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define FILEIO          freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define all(v)          v.begin(),v.end()
#define PR(a)           cout<<"("<<a<<")";
#define ED              cout<<'\n';
#define endl            '\n'
#define loop(j,a,n)     for(int j=a;j<=n;j++)
#define loop1(j,a,n)    for(int j=a;j>=n;j--)
#define fr1(j,n)        for(int j=0;j<n;j++)
#define fr(n)           for(int i=0;i<n;i++)
#define trav(x,s)       for(auto x:s)
#define SC(n)           scanf("%d",&n)
#define PB              push_back
#define MP              make_pair
#define pii             pair<int,int>
#define pll             pair<long long int,long long int>
#define F               first
#define S               second 
#define binf            2000000000000000001
#define mod             1000000007

const int N=1e5+99;

int n,k     ;
int a[N],dp[N][105],pf[N][105];

int main() 
{
    IO   

    cin>>n>>k;
    
    for(int i=1;i<=n;i++) cin>>a[i];

    
    for(int i=0;i<=k;i++) pf[i][0]=1;

    dp[0][0]=1;

    for(int i=1;i<=n;i++){
        for(int j=0;j<=k;j++)
        {
            dp[j][i]= (pf[j][i-1]);
            if(j-a[i]-1>=0) dp[j][i]= (dp[j][i]- pf[j-a[i]-1][i-1]+mod)%mod;

            pf[j][i]  = (dp[j][i] + (j?pf[j-1][i]:0))%mod;
            
        }
    }



    cout<<dp[k][n]<<endl;



}




 

Measured memory_bytes: 82304
from bisect import bisect_left

n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))

S.sort() # 昇順にソート

# binaryserch
def binarySearch(A, key):
	left, right = 0, len(A)
	while left < right:
		mid = (left + right) // 2
		if A[mid] == key:
			return True
		elif key < A[mid]:
			right = mid
		else:
			left = mid + 1
	return False

cnt = 0
for i in range(q):
	if binarySearch(S, T[i]): cnt += 1

print(cnt)


Measured memory_bytes: 16740
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n, W; cin>>n>>W;
    vector <int> v(n);
    vector <int> w(n);
    vector <vector<long long>> dp(n ,vector <long long>(100010,0));
    for(int i=0;i<n;i++){
    cin>>w[i]>>v[i];
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<100010;j++){
            if(j>=w[i]){
                if(i>0) dp[i][j]=max(dp[i-1][j-w[i]]+v[i],dp[i-1][j]);
                else dp[i][j]=v[0];
            }
            else {if(i>0) dp[i][j]=dp[i-1][j];
                else dp[i][j]=0;
            }
        }
    }
    cout<<dp[n-1][W]<<endl;
}

Measured memory_bytes: 79360
#include "bits/stdc++.h"
using namespace std;

int main() {
  int N;
  cin >> N;
  vector<int> a(N);
  int odd = 0;
  for(int i=0;i<N;i++){
    cin >> a[i];
    if(a[i] & 1) odd++;
  }
  if(odd%2){
    cout << "NO" ;
  }else{
    cout << "YES";
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define rep(i, n); for(ll i = 0; i < (ll)n; i++)

int main() {
  int n; cin >> n;
  int a,b;
  a = n/100; b = n%100;
  bool M1 = false;  if(a>0 && a<13) M1 = true;
  bool M2 = false;  if(b>0 && b<13) M2 = true;
  if(M1&&M2) cout << "AMBIGUOUS" << endl;
  if((!M1)&&M2) cout << "YYMM" << endl;
  if(M1&&(!M2)) cout << "MMYY" << endl;
  if((!M1)&&(!M2)) cout << "NA" << endl;
}

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

namespace AtCoder.Abc
{
    class QuestionC
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            // 整数配列の入力
            var num_AB = Console.ReadLine().Split(' '); //.Select(i => double.Parse(i)).ToArray();

            num_AB[1] = num_AB[1].Replace(".", "");

            var A = ulong.Parse(num_AB[0]);
            var B = ulong.Parse(num_AB[1]);

            var num_P = (A * B) / 100;

            Console.WriteLine(num_P);

            Console.Out.Flush();
        }
    }
}


Measured memory_bytes: 27556
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <string>
// #include <bits/stdc++.h>
#define ll long long; int
#define req(i,k) for(int i = 0; i < k; i++)
using namespace std;


int main(void) {
    int x , y;
   cin >> x >> y;
if(x == 1 && y == 1) {
    cout << 1000000;
    return 0;
}

if(x == 1) {
    x = 300000;
}  else if(x == 2) {
    x = 200000;
} else if (x == 3) {
    x = 100000;
}else {
    x = 0;
}

if(y == 1) {
    y = 300000;
} else if(y == 2) {
    y = 200000;
} else if(y == 3) {
    y = 100000;
}else {
    y = 0;
}

cout << x + y;
    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> Pll;
typedef pair<P,P> PP;
#define rep(i,a,n) for(ll i = a;i < n;i++)
#define repr(i,a,n) for(ll i = n-1;i >= a;i--)
#define LINF (ll)1e17
#define INF 1e9
#define MOD (ll)1e9+7
#define sMOD 1e5
#define fs first
#define sc second
#define setprecision(d) cout << fixed << setprecision(d);

ll gcd(ll a,ll b){
	if(!b) return a;
	return gcd(b,a%b);
	
}

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

signed main(){
	ll ans_w = 0,ans_a = 0,n,m;
	cin >> n >> m;

	bool is_ac[n] = {false};
	ll wa_cnt[n] = {};

	rep(i,0,m){
		string s;
		ll a;
		cin >> a >> s;

		if(s == "AC" && !is_ac[a-1]){
			ans_w += wa_cnt[a-1];
			ans_a++;
			is_ac[a-1] = true;
		}
		else if(s == "WA" && !is_ac[a-1]){
			wa_cnt[a-1]++;
		}
	}

	cout << ans_a << " " << ans_w << endl;
    return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vll vector<ll>
ll power(ll a, ll b, ll mod)
{
    ll c = 1;
    while (b > 0)
    {
        if (b % 2)
            c *= a, c %= mod;
        b /= 2;
        a *= a;
        a %= mod;
    }
    return c;
}
#define MAX 1000000007
#define quad pair<ll, ll>
#define x first
#define c second
ll n, c;
deque<quad> dq;
ll cost(quad q, ll y)
{
    return (q.x - y) * (q.x - y) + q.c;
}
bool chkdel(quad cur)
{
    quad q1 = dq[dq.size() - 1];
    quad q2 = dq[dq.size() - 2];
    bool f = ((cur.x-q2.x)*((q1.c-q2.c)+q1.x*(q1.x-q2.x))) >= ((q1.x-q2.x)*((cur.c-q2.c)+cur.x*(cur.x-q2.x)));  
    return f;
}
int main()
{
//#ifndef ONLINE_JUDGE
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> c;
    ll bp = 0, x;
    cin>>x;
    dq.push_back({x,bp+c});
    for (ll i = 1; i < n; i++)
    {
        cin >> x;
        
        while (dq.size() > 1 && cost(dq[0], x) >= cost(dq[1], x))
            dq.pop_front();
        bp = cost(dq.front(), x);
        quad q = {x, bp + c};
        while (dq.size() >= 2 && chkdel(q))
            dq.pop_back();
        dq.push_back(q);
        
    }
    cout << bp;
}

Measured memory_bytes: 2560
s=input()
ans=0
for i in range(len(s)):
    for j in range(len(s)):
        new_s=list(s[i:(len(s)-j)])
        if all((i in ["A","T","G","C"]) for i in new_s) and len(new_s)>ans:
            ans=len(new_s)
print(ans)

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

int main(){

  int n;
  cin>>n;
  vector<int> price(n);
  
  for (int i=0;i<n;i++){
    cin>>price.at(i);
  }
  
  sort(price.begin(),price.end());
  
  int answer=0;
  
  for (int i=0;i<n-1;i++){
    answer+=price.at(i);
  }
  
  answer+=price.at(n-1)/2;
  
  cout<<answer<<endl;
  
    

  
}
  













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

int main(){
  int n;cin>>n;
  int d,x;cin>>d>>x;
  int arr[n];
  for(int i=0;i<n;i++){
      cin >> arr[i];
  }
  

  int ans=0;
  for(int i=0;i<n;i++){
      int day=0;
      int param=0;
      while(true){
          day = param*arr[i]+1;

          //printf("day: %d\n",day);
          if(day<=d){
              ans ++;
              param ++;
          }else{
              break;
          }
          
      }
  }

    cout << ans + x << endl;
}

Measured memory_bytes: 3596