akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <sstream>
using namespace std;

int division(int a, int b)
{
    int res = a % b;
    return (res >= 0) ? res : b + a;
}

int attack(string line)
{
    static const string cmp[] = {"the", "this", "that"};
    istringstream iss(line);

    for (string word; iss >> word;) {
        char first = word[0];
        for (string c: cmp) {
            int i = 1;
            for (; i < c.size() && i < word.size(); i++)
                if (division(c[i] - 't', 26) != division(word[i] - first, 26))
                    break;
            if (i == c.size())
                return division('t' - first, 26);
        }
    }

    return 0;
}

inline int rotN(int x, int n)
{
    if (isalpha(x))
        return (x - 'a' + n) % 26 + 'a';
    else
        return x;
}

int main()
{
    int rot;
    string line;

    while (getline(cin, line)) {

        rot = attack(line);

        for (auto x : line)
            cout << (char) rotN(x, rot);

        cout << endl;
    }

    return 0;
}

Measured memory_bytes: 1192
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    string s;
    cin >> s;
    
    int cnt0 = 0;
    int cnt1 = 0;
    
    for (int i = 0; i < 2; i++){
        if (i == 0){
            for (int j = 0; j < s.size(); j++){
                if (j % 2 == 0 && s[j] != (char)(i + '0')) cnt0++;
                if (j % 2 != 0 && s[j] == (char)(i + '0')) cnt0++;
            }
        }
        else{
            for (int j = 0; j < s.size(); j++){
                if (j % 2 == 0 && s[j] != (char)(i + '0')) cnt1++;
                if (j % 2 != 0 && s[j] == (char)(i + '0')) cnt1++;
            }  
        }
    }
    
    cout << min(cnt0, cnt1) << endl;
}

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

int main(void){
	int n,a,b,c,d,count;
	while(scanf("%d",&n)!=EOF){
		count=0;
		for(a=0;a<=9;a++){
			for(b=0;b<=9;b++){
				for(c=0;c<=9;c++){
					for(d=0;d<=9;d++){
						if((a+b+c+d)==n){
							count++;
						}
					}
				}
			}
		}
		printf("%d\n",count);
	}
	}

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

#define rep(n) for(int i=0;i<n;i++)
#define repp(j, n) for(int j=0;j<n;j++)
#define reppp(i, m, n) for(int i=m;i<n;i++)
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define debug(x) cerr << #x << ": " << x << endl;

using namespace std;

typedef long long ll;
typedef pair<ll, ll> Pll;
typedef pair<int, int> Pii;
struct edge{int from, to; ll cost;};

const ll MOD = 1000000007;
const double EPS = 1e-9;

int main(){
    std::ios::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    vector<ll> a(n);
    rep(n) cin >> a[i];
    sort(all(a));

    Pll comb;
    comb.first = a[n-1];
    ll diff = INT_MAX;
    rep(n-1){
        ll adiff = abs(a[i] - ((comb.first+1) >> 1));
        if(adiff < diff){
            diff = adiff;
            comb.second = a[i];
        }
    }
    cout << comb.first << " " << comb.second << endl;
}


Measured memory_bytes: 1024
#include<stdio.h>

int search (long s[], long t[], int s_number, int t_number)
{
    int i, j;
    int answer = 0;

    for (i = 0; i < t_number; i++) {
      for (j = 0; j < s_number; j++) {
        if (t[i] == s[j]) {
          answer++;
          break;
        }
      }
    }
    return answer;
}

int main()
{

    unsigned long s[10000], t[500];
    int n, q, ncount, qcount;

    scanf("%d", &n);
    for (ncount = 0; ncount < n; ncount++)
      scanf("%d", &s[ncount]);

    scanf("%d", &q);
    for (qcount = 0; qcount < q; qcount++)
      scanf("%d", &t[qcount]);


    printf("%d\n", search(s, t, n, q));

    return 0;
}

Measured memory_bytes: 680
#include <stdio.h>
int main(void){
	int a, b, ans = 0;
	scanf("%d %d", &a, &b);
	for(int i = 0; i < 2; i++){
		if(a > b){
			ans += a;
			a--;
		}else{
			ans += b;
			b--;
		}
	}
	printf("%d", ans);
	return 0;
}

Measured memory_bytes: 128
using System;
using System.Linq;

namespace Algo
{
    class Program
    {
        static long GCD(long a, long b)
        {
            return b == 0 ? a : GCD(b, a % b);
        }

        static void Main()
        {
            var n = long.Parse(Console.ReadLine()!);
            var a = Console.ReadLine()?.Split().Select(long.Parse).ToArray();
            Console.WriteLine(a?.Aggregate(GCD));
        }
    }
}


Measured memory_bytes: 38576
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <set>
#include <utility>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>
#include <cstdio>
#include <map>

using namespace std;

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

#define rep(i,x) for(ll i = 0; i < (ll)(x); i++)
#define rrep(i,x) for(ll i = ((ll)(x) - 1); i >= 0; i--)

#define vi vector<int>
#define vvi vector<vi>

#define _upgrade ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define chmin(x,y) (x=min(x,y))
#define chmax(x,y) (x=max(x,y))

//ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

const ll mod = 1e9 + 7;
const ll IMF = 1LL<<29;
const double PI = 3.14159265358979323846;


// ***************************CODE**********************//

const int N = 1e5 + 7;

bool vis[N][100];


int suma(int n)
{
        int res = 0;
        while(n > 0)
        {
                res += n % 10;
                n /= 10;
        }
        return res;
}

int n;

void dfs(int r, int s)
{
        if(s >= 99) return;
        if(vis[r][s]) return;
        vis[r][s] = 1;
        for(int i = 0; i < 10; i++)
                dfs((10*r + i) % n, s + i);
}

int main()
{
        _upgrade;
        cin >> n;
        for(int i = 0; i < n; i++)
                dfs(i, suma(i));
        int res = 1e9;
        for(int i = 1; i < 99; i++){
                if(vis[0][i]) res = min(res,i);
        }
        cout << res << endl;
        return 0;
}







Measured memory_bytes: 233344
#include<bits/stdc++.h>
#define reg register
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
string a,b;
int main()
{
    cin>>a;
    b=a;
    reverse(a.begin(),a.end());
    for(reg int i=0;i<a.length();i++)
    {
        if(a[i]=='b')a[i]='d';
        else if(a[i]=='d')a[i]='b';
        else if(a[i]=='p')a[i]='q';
        else if(a[i]=='q')a[i]='p';
    }
    puts(a==b?"Yes":"No");
    return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include<cmath>
using namespace std;
int main()
{
    long long a,b,c,count;
    cin>>a>>b>>c;
        count=b/c-a/c;
        if(a%c==0) cout<<count+1<<endl;
        else cout<<count<<endl;
    return 0;
}

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

using namespace std;
typedef long long llint;
#define inf 1e18

llint k;
llint ans[55];
void solve(){
	cin >> k;
	for(int i=0;i<50;i++){
		ans[i]=(k+49)/50+i;
	}
	if(k%50){
			for(int i=0;i<50-(k%50);i++){
				ans[i]--;
			}
		}
	cout << 50 << endl;
	for(int i=0;i<50;i++){
		cout << ans[i] << " ";
	}
	cout << endl;
}

int main(int argc, char *argv[]) {
  solve();
  return 0;
}


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

int main()
{
    int N; cin >> N;
    string S[55];
    int T[55];
    for (int i = 1; i <= N; i++)
    {
        cin >> S[i] >> T[i];
    }
    string X; cin >> X;

    bool sleep = false;
    int ans = 0;
    for (int i = 1; i <= N; i++)
    {
        if (! sleep)
        {
            if (S[i] != X) continue;
            else sleep = true;
        }
        else
        {
            ans += T[i];
        }
    }

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

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

int main() {
  int A, B;
  cin >> A >> B;
  
  int count = 0;
  
  if (A > B){
    count += A;
    A--;
  } else {
    count += B;
    B--;
  }
  
  if (A > B){
    count += A;
    A--;
  } else {
    count += B;
    B--;
  }
  
  cout << count << endl;
  
}
  
  
    

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {


		Scanner sc = new Scanner(System.in);

		int hp = sc.nextInt();
		int attackType = sc.nextInt();
		for(int i =0;i < attackType; i++) {
			hp -= sc.nextInt();
			if(hp <= 0) {
				System.out.println("Yes");
				return;
			}
		}
		System.out.println("No");
	}
}

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

int main() {
  
  int r,g,b;
  cin >> r >> g >> b;
  
  if((g*10+b)%4 == 0){
    cout << "YES" << endl;
  }
  
  else{
    cout << "NO" << endl;
  }
  
}


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

using u32 = uint32_t;
using u64 = uint64_t;
using i32 = int32_t;
using i64 = int64_t;

int main()
{
	std::ios_base::sync_with_stdio(0);
	
	i32 a, b;

	std::cin >> a >> b;

	std::cout << std::max(0, (a-(2*b))) << "\n";
	
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		string s = Console.ReadLine();
		int Q = int.Parse(Console.ReadLine());
		int a = 0;
		int t1 = 250000;
		int t2 = 250000;
		int[]A = new int[500000];
		string[]S = new string[500000];
		int[]T = new int[500000];
		A[250000] = 1;
		S[1] = s;
		T[250000] = 0;
		for(var i=0;i<Q;i++){
			string[] str = Console.ReadLine().Split();
			int F = int.Parse(str[0]);
			if(F==1){
				a = (a+1)%2;
			} else {
				int F2 = int.Parse(str[1]);
				string s2 = str[2];
				if((F2+a)%2==1){
					t1--;
					A[t1] = i+2;
					S[i+2] = s2;
					T[t1] = a;
				} else {
					t2++;
					A[t2] = i+2;
					S[i+2] = s2;
					T[t2] = a;
				}
			}
		}
		if(a==0){
			for(var i=0;i<500000;i++){
				if(A[i]>0){
					Console.Write(S[A[i]]);
				}
			}
		} else {
			for(var i=499999;i>=0;i--){
				if(A[i]>0){
					if(i==250000){
                      	for(var j=S[1].Length-1;j>=0;j--){
                          	Console.Write(S[1].Substring(j,1));
                        }
                    } else {
						Console.Write(S[A[i]]);
                    }
				}
			}
		}
	}
}

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


int main()
{
    double w,h,x,y;
    cin >> w >> h >> x >> y;
    int ans = 0;
    if((int)w % 2 == 0 && (int)h % 2 == 0 && x == w/2 && y == h/2) ans = 1;
    cout << fixed << setprecision(10) << w*h/2 <<" " << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int
main()
{
  int a, b;
  cin >> a;
  cin >> b;
  if (a > b) {
    for (int i = 0; i < a; ++i) {
      cout << b;
    }
  }
  else {
    for (int i = 0; i < b; ++i) {
      cout << a;
    }
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 256
import bisect

n = int(input())
A = list(map(int, input().split()))
A.sort()
if len(A) == 2:
    print(A[1], A[0])
    exit()
m = A[-1]
xr = bisect.bisect(A, m/2)
LR = A[xr-1:xr+1]
r = LR[1] if m/2 - LR[0] > LR[1] - m/2 else LR[0]
print(m, r)

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

using namespace std;

int main()
{
    int N;
    while(cin >> N, N)
    {
        for(int i = 0; i < N; i++)
        {
            int x[3] = {}, y[3] = {}, z[3] = {}, w[3] = {};
            cin >> x[0] >> y[0] >> z[0] >> w[0] >> x[1] >> y[1] >> z[1] >> w[1];
            x[2] = x[0]*x[1] - y[0]*y[1] - z[0]*z[1] - w[0]*w[1];
            y[2] = x[0]*y[1] + y[0]*x[1] + z[0]*w[1] - w[0]*z[1];
            z[2] = x[0]*z[1] - y[0]*w[1] + z[0]*x[1] + w[0]*y[1];
            w[2] = x[0]*w[1] + y[0]*z[1] - z[0]*y[1] + w[0]*x[1];
            printf("%d %d %d %d\n", x[2], y[2], z[2], w[2]);
        }
    }
}

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

#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define vpii vector<pair<int,int>>
#define vpll vector<pair<ll,ll>>
#define fr(i,k,n) for (int i = k; i < n; ++i)
#define fri(i,k,n) for (int i = k; i >= n; --i)
#define INF (int)1e9
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define all(arr) arr.begin(),arr.end()

void boost(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

int n;

struct Mat
{
	vector<vll> A;
	Mat() {
		A.resize(n,vector<ll>(n,0));
	}
	void input(){
		fr(i,0,n)
		fr(j,0,n)
		cin>>A[i][j];
	}
	void identity(){
		fr(i,0,n)
		A[i][i]=1;
	}
	ll sum(){
		ll res=0;
		fr(i,0,n)
		fr(j,0,n)
		res=(res+A[i][j])%MOD;
		return res;
	}
	void operator*= (const Mat &B){
		Mat C=Mat();
		fr(i,0,n)
		fr(j,0,n)
		fr(k,0,n)
		C.A[i][j]=(C.A[i][j] + (A[i][k]*B.A[k][j])%MOD)%MOD;
		this->A=C.A;
	}
};

void solve(){
	ll k;
	cin>>n>>k;
	Mat M= Mat();
	M.input();
	Mat res=Mat();
	res.identity();
	while(k>0){
		if(k&1LL)
			res*=M;
		k>>=1LL;
		M*=M;
	}
	cout<<res.sum()<<endl;
	return;
}

int main()
{
	boost();
	
	int tc=1;
	//cin>>tc;
	while(tc--)
		solve();
	return 0;
}

Measured memory_bytes: 3724
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>

int main(void){
    int n,sum=0,s=0,count=0,last;
    scanf("%d",&n);
    for (int i=1; i<=n; i++){
        if (sum+i>n){
            break ;
        } else if (sum+i<=n){
            s=i;
            sum+=i;
        }
    }
    while (sum+s<=n){
        sum+=s;
        count++;
    }
    last=n-sum;
    for (int i=0; i<s-last; i++){
        printf("%d\n",i+1+count);
    }
    for (int i=0; i<last; i++){
        printf("%d\n",i+2+(s-last)+count);
    }
	return 0 ;
}

Measured memory_bytes: 128
#include<iostream>
#include<vector>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
using ll = long long;
using P = pair<int, int>;
#include<algorithm>
#include<math.h>
#include<map>
#include<queue>
#include<set>

const int mod = 2019;
const int INF = 1e16;
int main() {
	int n;
	cin >> n;
	vector<int>a(n);
	rep(i, n) {
		cin >> a[i];
	}
	ll sum(0);
	rep(i, n) {
		sum += a[i];
	}
	ll sum1(0);
	rep(i, n) {
		if (i % 2 == 1) {
			sum1 += 2 * a[i];
		}
	}
	vector<int>x(n);
	x[0] = sum - sum1;
	rep(i, n-1) {
		x[i + 1] = 2 * (a[i] - x[i] / 2);
	}
	rep(i, n) {
		cout << x[i] << " ";
	}
	return 0;
}

Measured memory_bytes: 4024
l=int(input())
a=[]
for i in range(l):
  m,n=(int(i) for i in input().split())
  a.append([n,m])
a.sort()
r="Yes"
s=0
for i in range(l):
  s=s+a[i][1]
  if s>a[i][0]:
    r="No"
    break
print(r)

Measured memory_bytes: 35648
import java.util.Scanner;
class Main{
    public static void main(String arg[]){
        Scanner scn=new Scanner(System.in);
        int a = scn.nextInt();
        int b = scn.nextInt(); 
        if(b>=a){
            System.out.println(a);
        }else{
            System.out.println(a-1);
        }
    }
}

Measured memory_bytes: 21332
#include<stdio.h>

int main()
{
    int i;
    int x,y,z;
    int count=0;
    scanf("%d %d %d",&x,&y,&z);
    for(i=x;i<y+1;i++){
        if(z%i==0){
            count++;
        }
    }
    printf("%d\n",count);
    return 0;
}



Measured memory_bytes: 2768
#include <iostream>
using namespace std;
int main(int argc, const char * argv[])
{
    int a,b,c;
    double ans;
    cin>>a>>b>>c;
    if(a>c && a>b) ans=c*b/2.0;
    else if(b>a && b>c) ans=a*c/2.0;
    else ans=a*b/2.0;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int main(){
	long long n;
	cin>>n;
	for(int i=sqrt(n);i>=0;i--){
		if(n%i==0){
			cout<<i-1+(n/i-1)<<endl;
			break;
		}
	}
}

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

int main(void){
  int n,m,x,y;
  int max = -1000;
  int min = 1000;
  scanf("%d %d %d %d\n",&n,&m,&x,&y);
  char str[10240];
  char *ptr;
  fgets(str,sizeof(str),stdin);
  fflush(stdin);

  ptr = strtok(str," ");
  while(ptr != NULL){
    if(max <= atoi(ptr)){
      max = atoi(ptr);
    }
    ptr = strtok(NULL," ");
  }

  int str_len = strlen(str);
  memset(str,'\0',str_len);

  fgets(str,sizeof(str),stdin);
  fflush(stdin);

  ptr = strtok(str," ");
  while(ptr != NULL){
    if(min >= atoi(ptr)){
      min = atoi(ptr);
    }
    ptr = strtok(NULL," ");
  }

  if((max < min && max < y) && (x < min && x < y)){
    printf("No War\n");
  }else{
    printf("War\n");
  }

  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define int long long
#define ll long long
using ull = unsigned long long;
using namespace std;
#define dump(x)                             \
    if (dbg) {                              \
        cerr << #x << " = " << (x) << endl; \
    }
#define overload4(_1, _2, _3, _4, name, ...) name
#define FOR1(n) for (ll i = 0; i < (n); ++i)
#define FOR2(i, n) for (ll i = 0; i < (n); ++i)
#define FOR3(i, a, b) for (ll i = (a); i < (b); ++i)
#define FOR4(i, a, b, c) for (ll i = (a); i < (b); i += (c))
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FORR(i, a, b) for (int i = (a); i <= (b); ++i)
#define bit(n, k) ((n >> k) & 1) /*nのk bit目*/
namespace mydef {
const int INF = 1ll << 60;
const int MOD = 1e9 + 7;
template <class T>
bool chmin(T& a, const T& b) {
    if (a > b) {
        a = b;
        return 1;
    } else
        return 0;
}
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    } else
        return 0;
}
void Yes(bool flag = true) {
    if (flag)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}
void No(bool flag = true) {
    Yes(!flag);
}
void YES(bool flag = true) {
    if (flag)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}
void NO(bool flag = true) {
    YES(!flag);
}
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T& val) {
    std::fill((T*)array, (T*)(array + N), val);
}
bool dbg = false;
}  // namespace mydef
using namespace mydef;
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(), (v).end()
#define SZ(x) ((int)(x).size())
#define vi vector<int>
#define vvi vector<vector<int>>
#define vp vector<pair<int, int>>
#define vvp vector<vector<pair<int, int>>>
#define pi pair<int, int>
//#define P pair<int, int>
//#define V vector<int>
//#define S set<int>
#define asn ans

int N, A[202020], B[202020];

void solve() {
    sort(A, A + N);
    sort(B, B + N);
    if (N % 2) {
        int n = N / 2;
        cout << B[n] - A[n] + 1 << endl;
    } else {
        int n = N / 2;
        int MIN = A[n] + A[n - 1];
        int MAX = B[n] + B[n - 1];
        cerr << MIN << " " << MAX << endl;
        cout << MAX - MIN + 1 << endl;
    }
}

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

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

    solve();
    return 0;
}


Measured memory_bytes: 6748
[N, x] = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
count = 0
i = 0
while x > 0 and i <= len(a):
  x -= a[i]
  if i == len(a)-1:
    if x != 0:
      break
  if x >= 0:
    count += 1
  i += 1
  
print(count)

Measured memory_bytes: 3064
# AOJ 0135 Clock Short Hand and Long Hand
# Python3 2018.6.18 bal4u

for _ in range(int(input())):
	h, m = list(map(int, input().split(':')))
	H, M = (30*h+(m//2))*2, (6*m)*2
	if (m & 1) == 1: H += 1
	a = H-M
	if a < 0: a = -a
	a2 = 720-a
	if a2 < a: a = a2
	if a < 60: print("alert")
	elif a >= 180 and a <= 360: print("safe")
	else: print("warning")


Measured memory_bytes: 5600
def main():
  
  N, M = (int(_) for _ in input().split())
  X = sorted([int(_) for _ in input().split()])
  if N >= M:
    print(0)
    return
  Y = sorted([X[i] - X[i-1] for i in range(1, M)])
  print(sum(Y[:M-N]))
  return

if __name__ == '__main__':
  main()

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

#define ll long long



void solve(){
    int a;
    cin>>a;
    if(a<1200){
        cout<<"ABC"<<endl;
    }   else{
        cout<<"ARC"<<endl;
    }
}

signed main(){
    //while(1)
    solve();
}

Measured memory_bytes: 256
fact = [1]
invfact = [1]
mod = 10 ** 9 + 7
h, w, a, b = map(int, input().split())
for i in range(1, h+w+1):
    fact.append((fact[-1] * i) % mod)
    invfact.append(pow(fact[i], mod - 2, mod))

ans = 0
for i in range(b, w):
    ans += (fact[h - a - 1 + i] * invfact[h - a - 1] * invfact[i]) * \
        (fact[a - 2 + w - i] * invfact[a - 1] * invfact[w - i-1])
    ans %= mod
print(ans)


Measured memory_bytes: 66928
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)x.size())
#define FOR(i,a,b) for (int i=a;i<=b;++i)
#define FORD(i,a,b) for (int i=a;i>=b;--i)
using namespace std;
typedef long long LL;
typedef pair<int,int> pa;
typedef vector<int> vec;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
char s[200010];
int n,f[200010][5];
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	f[1][1]=1;
	f[2][2]=1;
	f[3][3]=1;
	FOR(i,1,n)
		FOR(j,1,3) if (f[i][j]){
			FOR(k,1,3){
				if (i+k>n) break;
				if (j!=k){
					f[i+k][k]=max(f[i+k][k],f[i][j]+1);
					continue;
				}
				bool ok=0;
				FOR(l,1,j) if (s[i+l]!=s[i+l-j]) ok=1;
				if (ok) f[i+k][k]=max(f[i+k][k],f[i][j]+1);
			}
		}
	cout<<max(max(f[n][1],f[n][2]),f[n][3])<<endl;
	return 0;
}

Measured memory_bytes: 4352
N = int(input())
A = list(map(int, input().split()))  # 入力のときに N を使う必要はありません

count = 0

for i in range(N-2):
    first = A[i]
    second = A[i+1]
    third = A[i+2]
    if first < second:
        if second < third:
            count += 1
        else:
            count += 0
    else:
        if second > third:
            count += 1


print(count)

Measured memory_bytes: 3060
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<string> s(n);
    int count = 1;

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

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

    for (int i = 0; i < n - 1; i++)
    {
        if (s[i] != s[i + 1])
        {
            count++;
        }
    }

    cout << count << endl;
    return 0;
}

Measured memory_bytes: 9552
n = int(input())
scorelist = list(map(int, input().split(" ")))
color1 = len(set([int(i/400) for i in scorelist if i < 3200]))
color2 = len([i for i in scorelist if i >= 3200])
ans_min = max(1, color1)
ans_max = color1 + color2
print("{} {}".format(ans_min, ans_max))

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1000000007;

int d[2005];

ll f(int n){
  if(n < 3) return 0;
  if(d[n] != 0) return d[n];
  ll ans = 1;
  for(int i=3; i<n; ++i){
    ans += f(n-i);
    ans %= MOD;
  }
  return d[n] = ans;
}

int main(){
  int s;
  cin >> s;
  ll ans = f(s);
  cout << ans << endl;
}

Measured memory_bytes: 3656
import java.util.*;
 
public class Main {

    private static int MOD = 1_000_000_007;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int H = sc.nextInt();
        int W = sc.nextInt();
        int N = sc.nextInt();
        int b = Math.max(H, W);
        System.out.println((N+b-1)/b);
    }
}


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

typedef long long ll;

int main() {
    map<string,int> m;
    int q; cin >> q;
    for(int i=0; i<q; i++){
        int query;
        cin >> query;
        if(query==0){
            string key; int x;
            cin >> key >> x;
            m[key] = x;
        }
        else if(query==1){
            string key;
            cin >> key;
            cout << m[key] << endl;
        }
    }
}



Measured memory_bytes: 27748
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

/**
 * The Number of Island
 */
public class Main {

	final static int SEA = 0;
	final static int LAND = 1;
	final static int VISITED = -1;

	final static int[] V = { 1, -1, 0, 0 };
	final static int[] H = { 0, 0, 1, -1 };

	static LinkedList<Integer> xs, ys;
	static int count;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = "";

		int[][] map = new int[12][12];

		while (true) {
			// load map
			xs = new LinkedList<Integer>();
			ys = new LinkedList<Integer>();
			for (int i = 0; i < map.length; i++) {
				line = br.readLine();
				for (int j = 0; j < map[i].length; j++) {
					map[i][j] = line.charAt(j) - '0';
				}
			}

			// solve
			count = 0;
			for (int i = 0; i < map.length; i++) {
				for (int j = 0; j < map[i].length; j++) {
					if (map[i][j] == LAND) {
						xs.add(i);
						ys.add(j);
						while (!xs.isEmpty() && !ys.isEmpty()) {
							visit(map);
						}
						count++;
					}
				}
			}

			// output.
			System.out.println(count);

			// next
			line = br.readLine();
			if (line == null) {
				break;
			} else {
				continue;
			}
		}
		//
	}

	public static void visit(int[][] map) {

		int x, y;
		x = xs.remove();
		y = ys.remove();

		map[x][y] = VISITED;

		// next choices
		for (int i = 0; i < 4; i++) {
			int xv, yh;
			xv = x + V[i];
			yh = y + H[i];
			if (xv >= 0 && xv < 12 && yh >= 0 && yh < 12
					&& map[xv][yh] != VISITED && map[xv][yh] != SEA) {
				xs.add(xv);
				ys.add(yh);
			}
		}
	}
}

Measured memory_bytes: 120004
#include <bits/stdc++.h>
using namespace std;
const long long N = 1e5+5 , M = 998244353, OO = 0x3f3f3f3f;
typedef long long ll;
#define FIO ios_base::sync_with_stdio(0);cin.tie(0);
const double Pii = 3.14159265359;
ll n, m;

int main()
{
    FIO
    cin >> n >> m;
    if(n%2 == 1)
    {
        ll st = 1, en = (n/2)*2;
        for(int i=0; i<m; ++i)
        {
            cout << st << " " << en << endl;
            st++; en--;
        }
    }
    else
    {
        vector<ll> v;
        ll d1 = n-1;
        while(d1 > n/2)
        {
            v.push_back(d1);
            d1-=2;
        }
        ll d2 = (n/2)-1;
        if(d2%2 == 1) d2--;
        while(d2 > 0)
        {
            v.push_back(d2);
            d2-=2;
        }
        ll st = 1;
        for(int i=0; i<m; ++i)
        {
            cout << st << " " << st+v[i] << endl;
            st++;
        }
    }

    return 0;
}




Measured memory_bytes: 4156
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))

int main(){
	ll x,y;
	scanf("%lld%lld",&x,&y);
	printf("%lld",x*x-y);
}

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

#define rep(i, n) REP(i, 0, n)
#define repr(i, n) for (int i = (n); i >= 0; i--)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(m) cout << m << endl
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

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

    int wa[n] = {};
    int ac[n] = {};

    rep(i, m)
    {
        int p;
        string s;
        cin >> p >> s;
        p--;

        if (s == "AC")
            ac[p] = 1;
        else if (s == "WA" && ac[p] == 0)
            wa[p]++;
    }

    int cntac = 0, cntwa = 0;
    rep(i, n)
    {
        cntac += ac[i];
        if (ac[i] == 1)
            cntwa += wa[i];
    }

    cout << cntac << " " << cntwa << endl;

    return 0;
}

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

int n,d;
int count=0;
int main(){
  cin >> n >> d;
  int x[n][d];
  for(int i=0;i<n;i++)
    for(int j=0;j<d;j++)
      cin >> x[i][j];
  for(int i=0;i<n;i++){
    for(int k=i+1;k<n;k++){
      int r=0;
      for(int j=0;j<d;j++) r += pow(x[i][j] - x[k][j] ,2);
      float ans = sqrt(r);
      if(ceil(ans)==floor(ans)) count++;
    }
  }
  cout << count << endl;
  
  return 0;
}

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

int main() {
  int N;
  cin >> N;
  int tmp;
  int ans = 0;
  vector<int> Vs;
  vector<int> Benef;

  for(int i=0; i < N; i++){
      cin >> tmp;
      Vs.push_back(tmp);
  }
  for(int i=0; i < N; i++){
      cin >> tmp;
      Benef.push_back(Vs[i]-tmp);
  }

  sort(Benef.begin(), Benef.end());
  
  for(int i=N-1; i >= 0; i--){
      if(Benef[i] <= 0){
          break;
      }
      ans += Benef[i];
  }

  cout << ans << '\n';

  return 0;
}

Measured memory_bytes: 256
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;



int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);

    vector<long long> T(2, 0);
    vector<vector<long long>> S(2, vector<long long>(2, 0));

    for (int i = 0; i < 2; ++i) {
        cin >> T[i];
    }
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            cin >> S[i][j];
        }
    }

    long long PT = T[0] + T[1];
    vector<long long> D(2, 0);
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            D[i] += S[i][j] * T[j];
        }
    }

    if (D[0] == D[1] || S[0][0] == S[1][0]) {
        cout << "infinity\n";
        return 0;
    }

    if (S[0][0] > S[1][0]) {
        swap(S[0], S[1]);
        swap(D[0], D[1]);
    }
    
    if (D[0] < D[1]) {
        cout << 0 << '\n';
        return 0;
    }

    long long res = 0;
    long long diff = D[0] - D[1];
    long long A = (S[1][0] - S[0][0]) * T[0];
    res += 1;
    res += (A / diff) * 2;
    if (A % diff == 0) {
        --res;
    }

    cout << res << '\n';

    return 0;
}

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

#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, m, n) for(int i = (int)(m); i < (int)(n); ++i)

constexpr int MOD = 1e+9 + 7;


// 繰り返し二乗法(Exponentiation by squaring)
// n^8 = ((n^2)^2)^2 を利用する
template <typename T=long long>
T pow_mod(T n, T p, T m)
{
    if( p == 0 ) return 1;
    if( p%2 == 1 ) return pow_mod<T>(n, p-1, m) * n % m;
    else{
        T tmp = pow_mod<T>(n, p/2, m) % m;
        return tmp * tmp % m;
    }
}

// 2 以上 M 以下の素数をエラトステネスの篩を用いて求める, O( n * loglogn )
void calculatePrimeByEratosthenes( int M, std::vector<int>& prime )
{
    std::vector<bool> isPrime( M+1, true );  // isPrime[i]: i が素数かどうか
    isPrime[0] = isPrime[1] = false;
    for( int i = 2; i*i <= M; ++i ){
        if( isPrime[i] ){
            // 素数 i の倍数は素数ではない
            for( int j = 2; i*j <= M; ++j ) isPrime[i*j] = false;
        }
    }
    for( int i = 2; i <= M; ++i ){
        if( isPrime[i] ) prime.push_back( i );
    }
}


int main()
{
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i, N) cin >> A[i];


    // LCMを素因数分解した形で求める
    vector<int> prime;
    calculatePrimeByEratosthenes(*max_element(A.begin(), A.end()), prime);

    unordered_map<int, int> index;
    REP(i, N){
        int tmp = A[i];
        for(auto& p: prime){
            // 高速化に必要
            if(tmp == 1) break;
            if(tmp%p != 0) continue;
            int count = 0;
            while(tmp%p == 0){
                tmp /= p;
                ++count;
            }
            index[p] = max(index[p], count);
        }
    }

    // LCMを求める
    long long LCM = 1;
    for(auto idx: index){
        REP(i, idx.second){
            LCM *= idx.first;
            LCM %= MOD;
        }
    }

    // 答えを求める
    long long ans = 0;
    REP(i, N){
        ans += LCM * pow_mod<long long>(A[i], MOD-2, MOD);
        ans %= MOD;
    }
    cout << ans << endl;

    return 0;
}


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

int main()
{
    int x, k;

    cin >> k >> x;

    if (k*500 >= x) cout << "Yes" << endl;
    else cout << "No" << endl;
    
    return 0;
}

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

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

  if (x > a * a * b / 2) {
    theta = atan(2 * (a * a * b - x) / (a * a * a));
  } else {
    theta = atan((a * b * b) / (2 * x));
  }

  double PI = 3.14159265358979;
  theta = theta * 180 / PI;
  cout << fixed << setprecision(10) << theta;

  return 0;
}

Measured memory_bytes: 4072
import collections

n=int(input())
l=[]
for i in range(n):
    l.append(input())
l2=collections.Counter(l)
max=max(l2.values())

max_k_list = [kv[0] for kv in l2.items() if kv[1] == max]
l3=sorted(max_k_list)
print("\n".join(l3))



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

int cmp(char a,char b)
{
	return a>b;
}

int main()
{
	string s,t;
	cin>>s;
	cin>>t;
	sort(s.begin(),s.end());
	sort(t.begin(),t.end(),cmp);
	if (s<t)
		cout<<"Yes";
	else
		cout<<"No";
	return 0; 
} 

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

inline int read()
{
	int ret=0; char c=getchar();
	while(c<48||c>57)c=getchar();
	while(c>=48 && c<=57)ret=ret*10+c-48,c=getchar();
	return ret;
}
#define N 210005
int s,u,nn,m,n,tt,b[N],v[N],a[N];
long long ans;
int main()
{
	n=read();
	for(int i=1; i<=n; ++i){
		a[i]=read();
		if(a[i]){
			if(tt){
				ans+=(long long)(tt+1)*tt/2;
				b[++m]=0;
				v[m]=tt;
				tt=0;
			}
			++ans;
			b[++m]=a[i];
			v[m]=1;
		}else ++tt;
	}
	if(tt){
		ans+=(long long)(tt+1)*tt/2;
		b[++m]=0;
		v[m]=tt;
	}
//<
	for(int i=1; i<=m; ++i){
//		u=s=0;//  a[0]
        u=s=b[i];
		for(int j=i+1; j<=m; ++j){
			u^=b[j];
			s+=b[j];
			if(u==s)ans+=(long long)v[i]*v[j];else break;
		} 
	}
	
	cout<<ans;
}

Measured memory_bytes: 2560
import Control.Monad
import Control.Applicative

toClock :: Int -> [Int]
toClock time =
  let s = time `mod` 60
      m = time `div` 60
  in
      [m, s]

solver :: [Int] -> [Int]
solver = toClock . sum

main :: IO()
main = do
  times <- map (read :: String -> Int) <$> replicateM 4 getLine
  mapM_ print $ solver times

Measured memory_bytes: 3612
#include<cstdio>
#include<math.h>
#include<string>
#include<algorithm>
#include<functional>
#include<vector>
#include<set>
#include<map>
#include<iostream>
#include<queue>
#define INF 999999
#define EPS 1.0e-6

using namespace std;

int a,p;

int main()
{
    cin>>a>>p;
    cout<<(3*a+p)/2<<endl;
    
    return 0;
}

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

ll gcd(ll a, ll b){return b!=0 ? gcd(b, a%b) : a;}
ll lcm(ll a, ll b){return a / gcd(a, b) * b;}

int main(){
	int n;
	cin >> n;
	vector<int> a(n);
	rep(i, n) cin >> a[i];
	
	vector<ll> integral(n);
	integral[0] = a[0];
	for(int i = 1; i < n; ++i){
		integral[i] = integral[i-1] + a[i];
	}
	
	ll ans = INF;
	for(int i = 1; i < n; ++i){
		ll snuke = integral[i-1];
		ll arai = integral[n-1] - integral[i-1];
		ll sub = snuke - arai;
		if(sub < 0) sub *= -1;
		if(i == 1){
			ans = sub;
		}
		else{
			ans = min(ans, sub);
		}
	}
	cout << ans << endl;
	return 0;
}



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

int main() {
	int n=0;
	cin>>n;
	
	int a[n];
	
	int x[100001],y[100001];
	for(int i=1;i<100001;i++)
	x[i]=0;
	
	for(int i=0;i<n;i++)
	cin>>a[i];
	
	int ans1=0,ans2=0,ans=0;
	int mx=-99999;
	int val1=-7,val2=-8;
	///even index
	for(int i=0;i<=n-2;i+=2)
	{
	    x[a[i]]++;
	    if(mx<x[a[i]])
	    {
	        val1=a[i];
	        mx=x[a[i]];
	    }
	}
	mx=(n/2)-mx;
	ans1+=mx;
	///odd index
	for(int i=1;i<100001;i++)
	y[i]=0;
	mx=-99999;
	for(int i=1;i<=n-1;i+=2)
	{
	    y[a[i]]++;
	    if(mx<y[a[i]])
	    {
	        val2=a[i];
	        mx=y[a[i]];
	    }
	}
		mx=(n/2)-mx;
	ans2+=mx;
	ans=ans1+ans2;
	if(ans==0&&a[0]==a[1])
	{
	    cout<<(n/2)<<endl;
	}
	else if(val1!=val2)
	{
	   cout<<ans<<endl;
	}
	else
	{
	    int g1=0;
	    mx=-99999;
	    for(int i=1;i<100001;i++)
	    {
	        if(i!=val1&&x[i]>=mx)
	        {
	            g1=val1;
	            mx=x[i];
	        }
	    }
	    g1=(n/2)-mx;
	    
	    int g2=0;
	    mx=-99999;
	    for(int i=1;i<100001;i++)
	    {
	        if(i!=val2&&y[i]>=mx)
	        {
	            g2=val2;
	            mx=y[i];
	        }
	    }
	    g2=(n/2)-mx;
	    
	    if(g1>g2)
	    {
	        cout<<ans1+g2<<endl;
	    }
	    else if(g1<g2)
	    {
	        cout<<ans2+g1<<endl;
	    }
	    else
	    {
	        cout<<min(ans1,ans2)+g1<<endl;
	    }
	    
	}
	return 0;
}

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

int main(){
  int s,s1,s2,s3;
  cin >> s;
  s3=s%10,s2=(s%100-s3)/10,s1=(s%1000-s2-s3)/100;
  cout << s1+s2+s3 << endl;
}
  

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i, n) for (ll i = 0; i < n; i++)
#define rrep(i, n) for (ll i = n - 1; i >= 0; i--)
#define Rep(i, r, n) for (ll i = r; i < n; i++)
#define RRep(i, r, n) for (ll i = n - 1; i <= r; i--)
#define debug(x) cout << #x << ' ' << '=' << ' ' << (x) << endl;
#define fs first
#define sc second
#define int long long
#define pb push_back
const int dx[] = {0, -1, 0, 1};
const int dy[] = {1, 0, -1, 0};
const int MOD = (1000000007);
//const int MOD = (998244353);
//const int INF = (1 << 30)-1;
const int INF = (1LL << 60) - 1;
const double EPS = (1 >> 30);

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

using Graph = vector<vector<pair<int, int>>>;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(10);
    //---------------------------------------------

    int k,a,b;
    cin>>k>>a>>b;
    ll ans=0;
    if(b-a>=3){
        if(k+1<=a){
            cout<<k+1<<endl;
        }
        else{
            k-=a-1;
            ans=a;
            ans+=((int)(k/2))*(b-a);
            ans+=k%2;
            cout<<ans<<endl;
        }
    }
    else{
        cout<<1+k<<endl;
    }
    
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<bitset>
#include<unordered_map>
#include <climits>
#include<fstream>
using namespace std;
//---------------------------------------------------
//library zone!!!!!
typedef long long ll;
typedef long double ld;
#define rep(i,j) for(ll i=0;i<(long long)(j);i++)
#define all(a) (a).begin(),(a).end()
const ll Mod = 1000000007;
struct P {
	ll pos, cost;
};
bool operator<(P a, P b) { return a.cost < b.cost; }
bool operator>(P a, P b) { return a.cost > b.cost; }
struct B {
	ll to, cost;
};
struct E {
	ll from, to, cost;
};
bool operator<(E a, E b) {
	return a.cost < b.cost;
}
struct H {
	ll x, y;
};
bool operator<(H a, H b) {
	if (a.x != b.x) return a.x < b.x;
	return a.y < b.y;
}
bool operator>(H a, H b) {
	if (a.x != b.x) return a.x > b.x;
	return a.y > b.y;
}
bool operator==(H a, H b) {
	return a.x == b.x&&a.y == b.y;
}
bool operator!=(H a, H b) {
	return a.x != b.x || a.y != b.y;
}
ll gcd(ll i, ll j) {
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcd(j%i, i);
}
ld mod_pow(ld x, ll n, ll p) {
	ld res = 1;
	while (n > 0) {
		if (n & 1) res = res * x;
		x = x * x;
		n >>= 1;
	}
	return res;
}//x^n%p
const ll Inf = 3023372036854775807;
const int inf = 1500000000;
#define int long long
//----------------------------------------------------
//++++++++++++++++++++++++++++++++++++++++++++++++++++
int n;
int a[300000], b[300000];
signed main() {
	cin >> n;
	int ans = 0, mi = Inf;
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
		ans += a[i];
		if (a[i] > b[i]) {
			mi = min(mi, b[i]);
		}
	}
	cout << max(0ll, ans - mi) << endl;
}

Measured memory_bytes: 2432
import java.util.*;
import java.io.*;

class Main
{
    public static void main(String[] args) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split("\\s");
        int n = Integer.parseInt(s[0]);
        int k = Integer.parseInt(s[1]);
        String[] ss = br.readLine().split("\\s");
        int[] arr = new int[n];
        for(int i = 0; i < n; i++)
        {
            arr[i] = Integer.parseInt(ss[i]);
        }
        double[][] dp = new double[n+1][k+1];
        double mod = Math.pow(10,9)+7;
        for(int j = 0; j <= k; j++)
        {
            dp[1][j] = (arr[0]>=j)?1:0;
        }
        for(int i = 2; i <= n; i++)
        {
            for(int j = 0; j <= k; j++)
            {
                if(j == 0)
                    dp[i][j] = dp[i-1][j];
                else
                {
                    dp[i][j] = (dp[i-1][j] + dp[i][j-1])%mod;
                    if(j-arr[i-1] > 0)
                    {
                        dp[i][j] = (dp[i][j] - dp[i-1][j-arr[i-1]-1] + mod)%mod;
                    }
                }
            }
        }
        System.out.println((int)dp[n][k]);
    }
}

Measured memory_bytes: 125820
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {

        Boolean flag = false;
        
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        out_of_loop:
        for (int i = 0; ; i++){

			if (4 * i > n)break;
          
            for (int j = 0; ; j++){
                int sum = 4 * i + 7 * j;
                
                if (sum > n)break;
                
                if (sum == n){
                    flag = true;
                    break out_of_loop;
                }
            }
        }
        
        if (flag)
            System.out.println("Yes");
        else
            System.out.println("No");
        
        sc.close();
    }
}



Measured memory_bytes: 23636
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
 
int main()
{
    int a[101][101], b[101], c[101];
    int i, j;
    int n, m;
 
    scanf("%d%d", &n, &m);
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) scanf("%d", &a[i][j]);
    }
    for (j = 0; j < m; j++) scanf("%d", &b[j]);
 
    for (i = 0; i < n; i++) {
        c[i] = 0;
        for (j = 0; j < m; j++) c[i] += a[i][j] * b[j];
    }
 
    for (i = 0; i < n; i++) {
        printf("%d\n", c[i]);
    }
    return 0;
}


Measured memory_bytes: 2108
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
constexpr int di[] = { 0, 1, 0, -1 }, dj[] = { 1, 0, -1, 0 };
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define SORTR(v) sort((v).rbegin(), (v).rend())
#define all(v) (v).begin(), (v).end()
#define N 100005
constexpr ll inf = 100000000000000;
/*cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);*/
vector<vector<int>> dist;
vector<vector<char>> maze;
int h,w;
bool check(int mid){

  return false;
}

ll serch(ll ok,ll ng) {
	while (abs(ok-ng) > 1) {
		ll mid = (ok + ng) / 2;
		if (check(mid))ok = mid;
		else ng = mid;
	}
	return ok;
}

int bfs(int x ,int y){
  vector<vector<bool>> visited(h,vector<bool>(w,false));
  visited[x][y]=true;
  rep(i,h){
    rep(j,w){
      dist[i][j]=0;
    }
  }
  queue<P> q;
  q.push(make_pair(x,y));
  while(!q.empty()){
    P nq=q.front();q.pop();
    visited[nq.first][nq.second]=true;
    rep(i,4){
      int nx=nq.first+di[i];
      int ny=nq.second+dj[i];
      if(0<=nx&&nx<h&&0<=ny&&ny<w&&maze[nx][ny]=='.'&&!visited[nx][ny]){
        q.push(make_pair(nx,ny));
        visited[nx][ny] = true;
        dist[nx][ny]=dist[nq.first][nq.second]+1;
      }
    }
  }
  int m=0;
  rep(i,h){
    rep(j,w){
      m=max(m,dist[i][j]);
    }
  }
  return m;
}


int main(){
  cin>>h>>w;
  dist.resize(h);
  maze.resize(h);
  rep(i,h){
    dist[i].resize(w);
    maze[i].resize(w);
    rep(j,w){
      cin>>maze[i][j];
    }
  }
  int ans=0;
  rep(i,h){
    rep(j,w){
      if(maze[i][j]=='.'){
        ans=max(ans,bfs(i,j));
      }
    }
  }
  cout<<ans<<endl;
}



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



int main()
{
    int cnt = 0;
    std::string s;
    std::cin>>s;
    for(int i=0, j=s.size()-1;i<s.size()/2; i++,j--)
    {
        if(s[i]==s[j]) continue;
        else cnt++;
    }

    std::cout<<cnt<<'\n';
    return 0;
}


Measured memory_bytes: 256
n,m=map(int,input().split())
a=list(map(int, input().split()))
num=sum(a)
tmp=float(num)/float(4.0*m)
count=0
for i in range(n):
  if a[i]>=tmp:
    count+=1
if count>=m:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3060
#include <map>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int n, p[109], dp1[109][209][209], dp2[109][209][209], ptr[20009]; bool vis[109][209][209]; vector<int> q, G[109];
void calc_evaluation(int pos) {
	if (G[pos].size() == 0) return;
	p[pos] = -999999999;
	for (int i : G[pos]) {
		calc_evaluation(i);
		p[pos] = max(p[pos], -p[i]);
	}
}
void solve(int pos, int alpha, int beta) {
	if (G[pos].size() == 0) {
		dp1[pos][ptr[alpha + 10001]][ptr[beta + 10001]] = 1;
		dp2[pos][ptr[alpha + 10001]][ptr[beta + 10001]] = 1;
		return;
	}
	if (vis[pos][ptr[alpha + 10001]][ptr[beta + 10001]]) return;
	vector<int> perm(G[pos].size());
	for (int i = 0; i < perm.size(); i++) perm[i] = i;
	int ret1 = n, ret2 = 0;
	do {
		int alpha2 = alpha, beta2 = beta, cnt_min = 0, cnt_max = 0;
		for (int i = 0; i < perm.size(); i++) {
			int chl = G[pos][perm[i]];
			int val = -p[chl];
			solve(chl, -beta2, -alpha2);
			cnt_min += dp1[chl][ptr[-beta2 + 10001]][ptr[-alpha2 + 10001]];
			cnt_max += dp2[chl][ptr[-beta2 + 10001]][ptr[-alpha2 + 10001]];
			if (val >= beta2) break;
			alpha2 = max(val, alpha2);
		}
		ret1 = min(ret1, cnt_min);
		ret2 = max(ret2, cnt_max);
	} while (next_permutation(perm.begin(), perm.end()));
	vis[pos][ptr[alpha + 10001]][ptr[beta + 10001]] = true;
	dp1[pos][ptr[alpha + 10001]][ptr[beta + 10001]] = ret1;
	dp2[pos][ptr[alpha + 10001]][ptr[beta + 10001]] = ret2;
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) cin >> p[i];
	q.resize(2 * n);
	for (int i = 0; i < n; i++) q[i] = p[i], q[n + i] = -p[i];
	q.push_back(-10001);
	q.push_back(10001);
	sort(q.begin(), q.end());
	q.erase(unique(q.begin(), q.end()), q.end());
	for (int i = 0; i < q.size(); i++) ptr[q[i] + 10001] = i;
	for (int i = 0; i < n; i++) {
		int c, x; cin >> c;
		for (int j = 0; j < c; j++) {
			cin >> x; x--;
			G[i].push_back(x);
		}
	}
	calc_evaluation(0);
	solve(0, -10001, 10001);
	cout << dp1[0][0][q.size() - 1] << ' ' << dp2[0][0][q.size() - 1] << endl;
	return 0;
}

Measured memory_bytes: 10676
N  = int(input())
time = [0] * N
for i in range(1, N):
    C, S, F = map(int, input().split())
    for j in range(i):
        if time[j] <= S:
            time[j] = S + C
        elif time[j] % F == 0:
            time[j] += C
        else:
            time[j] = (time[j] // F + 1)* F + C
for i in range(N):
    print(time[i])

Measured memory_bytes: 3064
# coding:utf-8

import sys
from collections import defaultdict, deque

INF = 10 ** 5
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


n, m = LI()

G = defaultdict(list)
G2 = defaultdict
in_degree = [0] * n
for _ in range(m):
    x, y = LI_()
    G[x].append(y)
    in_degree[y] += 1

# トポロジカルソート
q = deque()
for v, e in enumerate(in_degree):
    if e == 0:
        q.append(v)

res = []
while q:
    v = q.popleft()
    res.append(v)
    for nv in G[v]:
        in_degree[nv] -= 1
        if in_degree[nv] == 0:
            q.append(nv)

dp = [0] * n
for v in res:
    for nv in G[v]:
        dp[nv] = max(dp[nv], dp[v] + 1)

print(max(dp))


Measured memory_bytes: 32384