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

int main(){
	int n;
	cin >> n;
	int a[n],b[n],c[n];
	for(int i = 0;i<n;i++)cin >> a[i];
	for(int i = 0;i<n;i++)cin >> b[i];
	for(int i = 0;i<n-1;i++)cin >> c[i];
	int sum = b[a[0]-1];
	for(int i = 1;i<n;i++){
		sum += b[a[i]-1];
		if(a[i] - a[i-1] == 1)sum+=c[a[i-1]-1];
	}
	cout << sum << endl;
}

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

bool solve(){
    int n, r;
    cin >> n >> r;
    if(n == 0) return false;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        a[i] = n-i;
    }
    for(int i=0;i<r;i++){
        int p, c;
        cin >> p >> c;
        p--;
        vector<int> tmp(c);
        for(int j=0;j<c;j++){
            tmp[j] = a[p+j];
        }
        a.erase(a.begin()+p, a.begin()+p+c);
        a.insert(a.begin(), tmp.begin(), tmp.end());
    }
    cout << a.front() << endl;
    return true;
}

int main(){
    while(solve());
    return 0;
}


Measured memory_bytes: 3040
#include <stdio.h>

int main(void){

	int n;
	int i;
	long int max = -1000001;
	long int min = 1000001;
	long int sum = 0;
		
	scanf("%d", &n);
	
	int num[n];
	
	for(i=0; i<n; ++i){
		scanf("%d", &num[i]);
	}
	
	for(i=0; i<n; ++i){
		if(num[i]>max){
			max=num[i];
		}
		
		if(num[i]<min){
			min=num[i];
		}
		
		sum=sum+num[i];
	}
	
	printf("%ld %ld %ld\n",min, max, sum);
	
	return 0;
}

Measured memory_bytes: 2788
# -*- coding: utf-8 -*-
 
import math
import itertools
import sys
import copy
 
# 入力
#A, B, C, D = map(int, input().split())
#L = list(map(int, input().split()))
#S = list(str(input()))
#N = int(input())
#K, X = map(int, input().split())

N = int(input())
S = str(input())

cnt = 0
for i in range(N) :
  if S[i:i+3] == "ABC" :
    cnt += 1
    
print (cnt)


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

int M[3][30];

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

  int N,C;
  cin >> N >> C;

  int D[500][500];
  rep(i, C) {
    rep(j, C) {
      cin >> D[i][j];
    }
  }

  rep(i, N) {
    rep(j, N) {
      int c; cin >> c;
      c--;
      M[(i+j)%3][c]++;
    }
  }

  int ans = 1e9;

  rep(i, C) {
    rep(j, C) {
      if(i == j) continue;
      rep(k, C) {
        if(i == k || j == k) continue;
        int sum = 0;

        rep(l, C) {
          sum += M[0][l] * D[l][i];
          sum += M[1][l] * D[l][j];
          sum += M[2][l] * D[l][k];
        }

        ans = min(ans, sum);
      }
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define each(i,a) for(auto&&i:a)
#define vv(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__))
using namespace std;
using ll=long long;
const ll MOD=1000000007;
const ll LINF=0x1fffffffffffffff;
const vector<ll> four={0,1,0,-1,0};
using tuplis=pair<ll,pair<ll,ll>>;
template<class T>using pq=priority_queue<T,vector<T>,greater<T>>;
template<class T>inline constexpr bool update_min(T&a,const T&b){if(a>b){a=b;return 1;}return 0;}
template<class T>inline constexpr bool update_max(T&a,const T&b){if(a<b){a=b;return 1;}return 0;}


ll n=100002;
vector<ll>h(n),mem(n,LINF);
ll dp(ll i){
    if(i<1)return LINF;
    if(i==1)return 0;
    if(mem[i]!=LINF)return mem[i];
    mem[i]=min(dp(i-1)+abs(h[i-1]-h[i]),dp(i-2)+abs(h[i-2]-h[i]));
    return mem[i];
}
signed main(){
    cin>>n;
    rep(i,1,n+1)cin>>h[i];
    cout<<dp(n);
}





Measured memory_bytes: 4224
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a); i > (b); i--)
#define ALL(a) (a).begin(), (a).end()
const ll MOD = 1e9 + 7;
 
ll power(int x, int y) {
    if (y == 0) return 0;
    if (y == 1) return x;
    ll p = power(x, y >> 1);
    if (y & 1) return p * p % MOD * x % MOD;
    else return p * p % MOD;
}
 
int main() {
    int N;
    cin >> N;
    ll ans = power(10, N) - 2 * power(9, N) + power(8, N);
    cout << (ans + 2 * MOD) % MOD << endl;
    return 0;
}

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

int main(){
    while(true){
        int n;
        cin>>n;
        if(n==0){
            break;
        }
        double s[n],m=0.0,sigma=0.0;
    
        for(int i=0;i<n;i++){cin>>s[i];m+=s[i];}
        m=m/n;
        for(int i=0;i<n;i++){
            sigma+=(s[i]-m)*(s[i]-m);
        }
        sigma=sigma/double(n);
        cout<<sqrt(sigma)<<endl;
    }
    return 0;
}


Measured memory_bytes: 3268
#include<bits/stdc++.h>
     
    using namespace std;
     
    #define all(x) x.begin(), x.end()
    typedef vector<int> vi;
    typedef pair<int,int> ii;
    typedef long long ll;
     
    const ll inf = 3e18 + 5;
    const int maxn = 2e5+1;
    
    vector<int> adjlist[maxn];
    bool visited[maxn];
    ll value[maxn];
    ll res[maxn];
    
    void dfs(int n, ll acc){
        
        if(visited[n])
            return;
        visited[n]=true;
        acc+=value[n];
        res[n]=acc;
        for(int x : adjlist[n]){
            dfs(x, acc);
        }
    }
    
    int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(0);
    
        int n,q;
        cin >> n >> q;
        
        for(int i=0; i<n-1; i++){
            int ai, bi;
            cin >> ai >> bi;
            adjlist[ai].push_back(bi);
            adjlist[bi].push_back(ai);
        }
        
        for(int i=0; i<q; i++){
            int pi, xi;
            cin >> pi >> xi;
            value[pi]+=xi;
        }
        dfs(1,0);
        for(int i=1; i<n+1; i++)
            cout << res[i] << endl;
    }

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

using namespace std;

int n,l,dp[100005],a[100005];

int func(int i){

  if(i>n)return 0;
  if(dp[i]>0)return dp[i];
  if(a[i]>a[i-1] && a[i]>a[i+1])return dp[i]=l-a[i];

  int res=0;
  if(a[i]<a[i-1])res=max(res,func(i-1));
  if(a[i]<a[i+1])res=max(res,func(i+1));

  return dp[i]=l-a[i]+res;
}

int main(void){
  
  while(cin >> n >> l){
    
    for(int i=0;i<n+2;i++)dp[i]=0;

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

    a[0]=a[n+1]=0;

    int res=0;
    for(int i=1;i<n+1;i++)
      res=max(res,func(i));

    cout << res << endl;
  }
  
  return 0;
}

Measured memory_bytes: 3120
#include <iostream>
#include <sstream>
#include <stack>
#include <iomanip>
#include <string>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <queue>
#include <cmath>

#define BEGIN(x) x.begin()
#define END(x) x.end()
#define ALL(x) BEGIN(x), END(x)
#define PAIR make_pair
#define VEC(type) vector<type >

#define FOR(i, A, B) for(auto i = (A);i != (B); i++)
#define FORD(i, A, B) for(auto i = (A);i != (B); i--)

#define READRANGE(begin, end) FOR(it, begin, end) cin >> *it
#define READVEC(V) READRANGE(BEGIN(V), END(V))

using namespace std;

typedef long long lint;
typedef pair<int, int> Pii;
typedef pair<int, lint> Pil;
typedef pair<lint, lint> Pll;
typedef pair<lint, int> Pli;

// ---- BEGIN LIBRARY CODE ----
// ---- END LIBRARY CODE ----
void io_init()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
};

int main(int argc, char **argv)
{
    io_init();

    // Actual program code starts here.
    int N, K;
    string S;
    cin >> N >> K >> S;
    S[K - 1] ^= 32;
    cout << S << endl;
    return 0;
};


Measured memory_bytes: 256
/**
 *    author:  math2do
 *    created: 05.09.2020 12:49:26
**/

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector <int> arr(n);
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
  } 
  vector <vector <long long> > dp(n, vector <long long>(n));
  for (int i = n - 1; i >= 0; i--) {
    for (int j = i; j < n; j++) {
      if (i == j) {
        dp[i][j] = arr[i];
        continue;
      }     
      dp[i][j] = max(arr[i] - dp[i + 1][j], arr[j] - dp[i][j - 1]);
    } 
  } 
  cout << dp[0][n - 1] << endl;
  return 0;
}


Measured memory_bytes: 73696
#include<bits/stdc++.h>
using namespace std;
int main(){
int A ,B ,C ;
cin >> A >> B >> C ;
if ( A <= C && C <= B ){
cout << B - A << endl;
}
else if ( A <= B && B <= C ) {
cout << C - A << endl;
}
else if ( B <= A  && A <= C ){
cout << C - B << endl;
}
else if ( B <= C && C <= A){
cout << A - B << endl;
}
else if ( C <= A && A <= B ){
cout << B - C << endl;
}
else if  ( C <= B && B <= A ){
cout << A - C << endl;
}
}

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

int days[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool isLeap(int year){return (year%4 == 0 && (year%100 != 0 || year%400 == 0));}

int n, b[14][7], C[100], num[10]={6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

int check(char c, int idx){
  
  int d=c-'0', res=0;
  
  if(b[idx][0]){
    
    if(d==0||d==2||d==3||d==5||d==6||d==7||d==8||d==9) res++;
      
  }
  if(b[idx][1]){

    if(d==0||d==4||d==5||d==6||d==8||d==9) res++;
    
  }
  if(b[idx][2]){
    
    if(d==0||d==1||d==2||d==3||d==4||d==7||d==8||d==9) res++;
    
  }
  if(b[idx][3]){
    
    if(d==2||d==3||d==4||d==5||d==6||d==8||d==9) res++;
    
  }
  if(b[idx][4]){
    
    if(d==0||d==2||d==6||d==8) res++;
    
  }
  if(b[idx][5]){
    
    if(d==0||d==1||d==3||d==4||d==5||d==6||d==7||d==8||d==9) res++;
    
  }
  if(b[idx][6]){
    
    if(d==0||d==2||d==3||d==5||d==6||d==8||d==9) res++;
    
  }

  return res;
}

int cal(int h, int m, int s){
  
  string H=to_string(h);
  string M=to_string(m);
  string S=to_string(s);
  
  if(H.size()==1) H='0'+H;
  if(M.size()==1) M='0'+M;
  if(S.size()==1) S='0'+S;
  
  int res=0;
  
  for(int i=0;i<2;i++) res+=num[H[i]-'0'];
  for(int i=0;i<2;i++) res+=num[M[i]-'0'];
  for(int i=0;i<2;i++) res+=num[S[i]-'0'];
  
  res-=check(H[0], 8);
  res-=check(H[1], 9);
  res-=check(M[0], 10);
  res-=check(M[1], 11);
  res-=check(S[0], 12);
  res-=check(S[1], 13);
  
  return res;
}

int cal2(int y, int m, int d){
  
  string Y=to_string(y);
  string M=to_string(m);
  string D=to_string(d);
  
  while(Y.size()!=4) Y='0'+Y;
  if(M.size()==1) M='0'+M;
  if(D.size()==1) D='0'+D;
  
  int res=0;
  
  for(int i=0;i<4;i++) res+=num[Y[i]-'0'];
  for(int i=0;i<2;i++) res+=num[M[i]-'0'];
  for(int i=0;i<2;i++) res+=num[D[i]-'0'];
  
  res-=check(Y[0], 0);
  res-=check(Y[1], 1);
  res-=check(Y[2], 2);
  res-=check(Y[3], 3);
  res-=check(M[0], 4);
  res-=check(M[1], 5);
  res-=check(D[0], 6);
  res-=check(D[1], 7);
  
  return res;
}

void solve(){
  
  for(int h=0;h<=23;h++)
    
    for(int m=0;m<=59;m++)
      
      for(int s=0;s<=59;s++){
	
	int cnt = cal(h, m, s);
	
	C[cnt]++;
	
      }
  
  int ans = 0;
  
  int y=0, m=1, d=1;
  
  while(y<=9999){
    
    while(m<=12){
      
      while(d<=days[m]+(m==2&&isLeap(y))){
	
	int cnt = cal2(y, m, d);
	
	if(n-cnt>=0) ans+=C[n-cnt];
	
	d++;
      }
      
      d=1;
      
      m++;
    }
    
    m=1;
    
    y++;    
  }
  
  cout<<ans<<endl;
}

signed main(){
  
  cin>>n;
  
  int k;
  cin>>k;
  
  for(int i=0;i<k;i++){
    int p, q;
    cin>>p>>q;
    b[p][q]=1;
  }
  
  solve();
  
  return 0;
}



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

void solve() {
	string s;
	cin >> s;
	int n = (int) s.length();
	int whites = 0;
	long long cnt = 0;
	for (int i = n - 1; i >= 0; i--) {
		if (s[i] == 'B') {
			cnt += whites;
		} else {
			whites++;
		}
	}
	cout << cnt;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	solve();
}


Measured memory_bytes: 720
h, w = map(int, input().split())
g = ['']*h
for i in range(h):
  g[i] = input()

row = [False] * h
col = [False] * w
for i in range(h):
  for j in range(w):
    if g[i][j] == '#':
      row[i] = True
      col[j] = True

for i in range(h):
  if row[i]:
    for j in range(w):
      if col[j]:
        print(g[i][j], end='')
    print()


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


/* エイリアス */
#define ll long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vpi vector<pii>
#define vpll vector<pll>
#define endl '\n'

#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define em emplace
#define mp make_pair


/* 関数マクロ */
#define rep(i, n) for (ll i = 0; i < n; ++i)
#define rep2(i, n, m) for (ll i = n; i <= m; ++i)
#define rep3(i, n, m) for (ll i = n; i >= m; --i)
#define all(v) v.begin(), v.end()
#define si(v) int(v.size())
#define UNIQUE(v) sort(all(v)), v.erase(unique(all(v)),v.end())


/* 定数 */
const ll mod = 1e9 + 7;
const ll infll = (1LL << 62) - 1;
const ll inf = (1LL << 30) - 1;


/* その他 */
template<class S, class T> inline bool chmax(S &a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class S, class T> inline bool chmin(S &a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;


signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cout << fixed << setprecision(15);

  int n; cin >> n;
  string s; cin >> s;

  vi w(n+1,0), e(n+1,0);
  rep(i, n) w[i+1] += w[i] + (s[i] == 'W');
  rep(i, n) e[i+1] += e[i] + (s[i] == 'E');

  int ans = inf;
  rep(i, n) {
    chmin(ans, w[i] + (e[n] - e[i+1]));
  }

  cout << ans << endl;
}


Measured memory_bytes: 6120
#include <bits/stdc++.h>
#define xx first
#define yy second
#define mp make_pair
#define pb push_back
#define mset(x, y) memset(x, y, sizeof x)
#define mcpy(x, y) memcpy(x, y, sizeof x)
using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

inline int Read()
{
	int x = 0, f = 1, c = getchar();
	for (; !isdigit(c); c = getchar())
		if (c == '-')
			f = -1;
	for (;  isdigit(c); c = getchar())
		x = x * 10 + c - '0';
	return x * f;
}

const int MAXN = 45;
const int INF = 0x3f3f3f3f;

int n, m, xp, yp, ans, s[MAXN][MAXN], f[MAXN][MAXN][MAXN][MAXN];
char a[MAXN][MAXN];

inline int Sum(int xl, int xr, int yl, int yr)
{
	return s[xr][yr] + s[xl - 1][yl - 1] - s[xl - 1][yr] - s[xr][yl - 1];
}

int main()
{
#ifdef wxh010910
	freopen("data.in", "r", stdin);
#endif
	n = Read(), m = Read(), mset(f, INF), ans = INF;
	for (int i = 1; i <= n; i ++)
		scanf("%s", a[i] + 1);
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++)
			if (a[i][j] == 'P')
				xp = i, yp = j;
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++)
			s[i][j] = s[i - 1][j] + s[i][j - 1] + (a[i][j] == '#') - s[i - 1][j - 1];
	f[1][n][1][m] = 0;
	for (int xl = 1; xl <= n; xl ++)
		for (int xr = n; xr >= xl; xr --)
			for (int yl = 1; yl <= m; yl ++)
				for (int yr = m; yr >= yl; yr --)
					if (f[xl][xr][yl][yr] ^ INF)
					{
						int cur = f[xl][xr][yl][yr], val;
						if (xl <= xp && xp <= xr && yl <= yp && yp <= yr)
							ans = min(ans, cur + min(min(Sum(xl, xp, yl, yp), Sum(xl, xp, yp, yr)), min(Sum(xp, xr, yl, yp), Sum(xp, xr, yp, yr))));
						else
							ans = min(ans, cur);
						cur += Sum(xl, xr, yl, yr);
						for (int x = xl; x <= xr + 1; x ++)
							for (int y = yl; y <= yr + 1; y ++)
								if (!((x == xl || x == xr + 1) && (y == yl || y == yr + 1)))
								{
									val = Sum(xl, x - 1, yl, y - 1) + Sum(x, xr, y, yr);
									if (x > xl && y > yl && !(x <= xp && xp <= xr && y <= yp && yp <= yr))
										f[xl][x - 1][yl][y - 1] = min(f[xl][x - 1][yl][y - 1], cur - val);
									if (x <= xr && y <= yr && !(xl <= xp && xp < x && yl <= yp && yp < y))
										f[x][xr][y][yr] = min(f[x][xr][y][yr], cur - val);
									val = Sum(xl, x - 1, y, yr) + Sum(x, xr, yl, y - 1);
									if (x > xl && y <= yr && !(x <= xp && xp <= xr && yl <= yp && yp < y))
										f[xl][x - 1][y][yr] = min(f[xl][x - 1][y][yr], cur - val);
									if (x <= xr && y > yl && !(xl <= xp && xp < x && y <= yp && yp <= yr))
										f[x][xr][yl][y - 1] = min(f[x][xr][yl][y - 1], cur - val);
								}
					}
	return printf("%d\n", ans), 0;
}


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

using namespace std;
typedef long long ll;
#define rep(i,j,n) for (ll i = j; i < (n); i++)
#define CLR(mat,f) memset(mat, f, sizeof(mat))
#define IN(a, b, x) (a<=x&&x<b)
#define out(ans) cout << ans << endl
typedef pair<ll,ll>P;
const ll mod=1e9+7;
const int INF = 1000000;
const double PI=3.14159265359;

int main(){

  ll a,b,k;
  cin>>a>>b>>k;

  a=a-k;
  if(a<0){
    b+=a;
    a=0;
    if(b<0)b=0;
  }
  



  cout<<a<<" "<<b<<endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define EPS (1e-10)
#define equals(a, b) (fabs((a)-(b)) < EPS)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;

struct mint {
  ll x;
  mint(ll x=0):x((x%MOD+MOD)%MOD){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += MOD-a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= MOD; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
      mint a = pow(t>>1);
      a *= a;
    if (t&1) a *= *this;
      return a;
  }
   mint inv() const { return pow(MOD-2);}
   mint& operator/=(const mint a) { return *this *= a.inv();}
   mint operator/(const mint a) const { return mint(*this) /= a;}
};
typedef vector<mint> vm;
typedef vector<vm> vvm;

class Combi {
private:
  v(ll) fac, inv, finv;
  void init(int N) {
    fac[0] = fac[1] = 1; inv[1] = 1; finv[0] = finv[1] = 1;
    for (int i = 2; i < N; i++) {
      fac[i] = fac[i - 1] * i % MOD;
      inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
      finv[i] = finv[i - 1] * inv[i] % MOD;
    }
  }
public:
  Combi(int N) : fac(N + 1), inv(N + 1), finv(N + 1) { init(N + 1); }
  ll Cmod(int n, int k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
  }
  ll Pmod(int n, int k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * finv[n - k] % MOD;
  }
};
  
int main() {
  int n,m,k;
  cin >> n >> m >> k;
  Combi comb(n*m);
  mint ans = 0;
  srep(i,1,n) {
    ans += (ll(n-i)*m*m)*i;
  }
  srep(i,1,m) {
    ans += (ll(m-i)*n*n)*i;
  }
  ans *= comb.Cmod(n*m-2,k-2);
  cout << ans.x << endl;
  return 0;
}

Measured memory_bytes: 7980
#include<stdio.h>

int fib(int);

int main() {
  int n;

  scanf("%d", &n);

  printf("%d\n", fib(n));
  return 0;
}

int fib(int n){
  int i, n1, n2, n3;
  
  if(n == 0 || n == 1) {
    return 1;
  } else {
    n1 = n2 = n3 = 1;
    for(i = 0 ; i < n-1 ; i++){
      n1 = n2;
      n2 = n3;
      n3 = n1 + n2;
    }
    return n3;
  }
}



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

int dp[11][1010];

int main(){
	int d, g;
	cin >> d >> g;
	vector<int>p(d + 1), c(d + 1);
	for (int i = 1;i <= d;i++) {
		cin >> p[i] >> c[i];
	}

	for (int i = 0;i <= 10;i++) {
		for (int j = 0;j <= 1000;j++) {
			dp[i][j] = 0;
		}
	}
	for (int i = 1;i <= d;i++) {
		for (int j = 0;j < p[i];j++) {
			for (int k = 0;k + j <= 1000;k++) {
				dp[i][k + j] = max(dp[i][k + j], dp[i - 1][k] + i * 100 * j);
			}
		}
		for (int k = 0;k + p[i] <= 1000;k++) {
			dp[i][k + p[i]] = max(dp[i][k + p[i]], dp[i - 1][k] + i * 100 * p[i] + c[i]);
		}
	}
	for (int i = 0;i <= 1000;i++) {
		if (dp[d][i] >= g) {
			cout << i << endl;
			return 0;
		}
	}



	return 0;
}

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

typedef long long int LL;
typedef long long int LLint;

//Faster Program
#define endl "\n"

//Faster Coding
#define ED return
#define GET(a) int a;cin >> a
#define DGET(a) double a;cin >> a
#define SGET(a) string a;cin >> a
#define CGET(a) char a;cin >> a
#define PRINT(a) cout << a << "\n"
#define ANS(a,b) int a;cin >> a;cout << b << "\n"
#define FOR(n) for(int i = 0;i < n;i++)
#define SORT(vec) sort(vec.begin(),vec.end())
#define REV(vec) reverse(vec.begin(),vec.end())

//As Function
#define UP(a,b) ((a+(b-1))/b)
#define ipow(x,y) LL(pow(x,y))

//Debug
#define TEST cout << "OK\n"

const double PI = M_PI;
const long long INF = int(999999999);
const long long MOD = int(1000000007);

//Settings
const bool DO_BENCHMARK = false;
const int DOUBLE_ACCURACY = 15;

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(DOUBLE_ACCURACY);
    void solve();
    if(DO_BENCHMARK){
        clock_t clock_start = clock();
        solve();
        clock_t clock_end = clock();
        const double time = static_cast<double>(clock_end-clock_start)/CLOCKS_PER_SEC*1000.0;
        cout << "\n" << time << "[ms]\n";
    }
    else solve();
}

void solve(){
    GET(X);
    GET(Y);
    if(X+Y == 2){
        PRINT(1000000);
        ED;
    }
    int ans = 0;
    switch (X) {
    case 1:ans+=300000;
        break;
    case 2:ans+=200000;
        break;
    case 3:ans+=100000;
        break;
    default:
        break;
    }
    switch (Y) {
    case 1:ans+=300000;
        break;
    case 2:ans+=200000;
        break;
    case 3:ans+=100000;
        break;
    default:
        break;
    }
    PRINT(ans);
}


Measured memory_bytes: 256
// WeirdBugsButOkay

#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define pii pair <int, int>
#define pll pair <ll, ll>
#define mp make_pair
#define pb push_back
#define ff first
#define ss second

using namespace std;

const ll N = 200001;
ll a[N], vis[N];
ll ccs, pl;
vector <ll> seq;

void dfs(ll u, ll p = 0)
{
    vis[u] = vis[p] + 1;
    seq.pb(u);
    ll v = a[u];
    if(!vis[v])
        dfs(v, u);
    else
        ccs = vis[u] + 1 - vis[v];
}

void solve()
{
    ll n, x;
    cin >> n >> x;
    for(ll i = 1; i <= n; i++)
        cin >> a[i];
    dfs(1);
    pl = seq.size() - ccs;
    //cout << pl << ccs << endl;
    if(x < seq.size())
        cout << seq[x] << endl;
    else
    {
        ll tot = x - pl;
        tot %= ccs;
        cout << seq[pl + tot] << endl;
    }
}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int q = 1;
    //cin >> q;
    for(int i = 1; i <= q; i++)
    {
    	solve();
    }
    return 0;
}

Measured memory_bytes: 14028
#include <stdio.h>

#define WIDTH 10
#define HEIGHT 10

int field[ WIDTH ][ HEIGHT ];
const int range[ 4 ] = { 0, 4, 8, 12 };
const int dx[ 4 ][ 12 ] = { {}, { -1, 0, 1, 0 }, { -1, 0, 1, -1, 1, -1, 0, 1 }, { 0, -1, 0, 1, -2, -1, 1, 2, -1, 0, 1, 0 } };
const int dy[ 4 ][ 12 ] = { {}, { 0, -1, 0, 1 }, { -1, -1, -1, 0, 0, 1, 1, 1 }, { -2, -1, -1, -1, 0, 0, 0, 0, 1, 1, 1, 2 } };

int main( void ) {
	int i, x, y, size, white, max;

	while ( scanf( "%d,%d,%d", &x, &y, &size ) == 3 ) {
		field[ x ][ y ]++;

		for ( i = 0; i < range[ size ]; i++ ) {
			int nx = x + dx[ size ][ i ], ny = y + dy[ size ][ i ];

			if ( nx >= 0 && nx < WIDTH && ny >= 0 && ny < HEIGHT )
				field[ nx ][ ny ]++;
		}
	}

	white = 0;
	max = 0;
	for ( y = 0; y < HEIGHT; y++ )
		for ( x = 0; x < WIDTH; x++ )
			if ( !field[ x ][ y ] )
				white++;
			else if ( max < field[ x ][ y ] )
				max = field[ x ][ y ];

	printf( "%d\n%d\n", white, max );

	return 0;
}

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

int main(){
	int n;
	cin >> n;
	int tmp=n;
	int ans=0;
	while (n>0){
		ans+=n%10;
		n/=10;
	}
	if (tmp%ans==0) printf("Yes\n");
	else printf("No\n");
}

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

int n;
string s;
vector<vector<int>> memo;
vector<int> bf;
queue<int> qu;

string solve();

int main() {
  cin >> s;
  n = s.size();
  cout << solve() << endl;
  return 0;
}

string solve() {
  memo.assign(n + 1, vector<int>(26, n + 1));
  for (int i = n - 1; i >= 0; --i) {
    for (int j = 0; j < 26; ++j) memo[i][j] = memo[i + 1][j];
    memo[i][s[i] - 'a'] = i + 1;
  }
  qu.push(0);
  bf.assign(n + 2, -1);
  while (qu.size()) {
    int id = qu.front();
    qu.pop();
    for (int i = 0; i < 26; ++i) {
      int to = memo[id][i];
      if (bf[to] < 0) {
        bf[to] = id;
        if (to <= n)
          qu.push(to);
        else {
          string res(1, (char)(i + 'a'));
          while (id) {
            res += s[id - 1];
            id = bf[id];
          }
          reverse(res.begin(), res.end());
          return res;
        }
      }
    }
  }
  assert(0);
}

Measured memory_bytes: 30816
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define all(a) (a).begin(), (a).end()


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


Measured memory_bytes: 256
s = input().split(" ")
s = [int(i) for i in s]
A = s[0]
B = s[1]
K = s[2]

dic = {}
for i in range(K) : 
    if A+i <= B : 
        print(A + i)
        dic[A+i] = True

for i in reversed(range(K)):
    if B-i >= A:
        if not (B-i in dic):
            print(B-i)

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

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n; cin >> n;
	multiset<int> s;
	for(int i=0; i<(1<<n); ++i){
		int a; cin >> a;
		s.insert(a);
	}
	vector<int> v;
	v.push_back(*s.rbegin());
	s.erase(v[0]);
	for(int i=0; i<n; ++i){
		int m = v.size();
		for(int j=0; j<m; ++j){
			auto it = s.lower_bound(v[j]);
			if(it == s.begin()){
				cout << "No\n";
				return 0;
			}else{
				--it;
				v.push_back(*it);
				s.erase(it);
			}
		}
	}
	cout << "Yes\n";
}

Measured memory_bytes: 13688
#include <bits/stdc++.h>
#include <cassert>
typedef long long int ll;
using namespace std;

// @@ !! LIM()

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  ll N; cin >> N;
  vector<ll> A(N), B(N);
  for (ll i = 0; i < N; i++) {
    cin >> A.at(i) >> B.at(i);
  }
  sort(A.begin(), A.end());
  sort(B.begin(), B.end());
  if (N % 2 == 1) {
    ll m = N / 2;
    ll s = A.at(m);
    ll l = B.at(m);
    cout << l - s + 1 << endl;
  }else {
    ll m = N / 2;
    ll s = A.at(m - 1) + A.at(m);
    ll l = B.at(m - 1) + B.at(m);
    cout << l - s + 1 << endl;
  }

  return 0;
}



Measured memory_bytes: 6360
#include<bits/stdc++.h>
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int mod = 1000000007;
const int INF = 1001001001;

int main() {
  int n;
  cin >> n;
  vector<ll> l(n);
  rep(i, n) cin >> l[i];
  sort(l.rbegin(), l.rend());

  int ans = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      for (int k = j + 1; k < n; ++k) {
        
        ll a = l[i];
        ll b = l[j];
        ll c = l[k];
        if (a == b || b == c || c == a) continue;
        if (a < b + c) {
          ans++;
        }
      }
    }
  }
  cout << ans << endl;
}

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

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

    int max = -1;
    int answer;
  
  for (int i=1; i<(N+1); i++){
    int I = i;
     int c = 0;
    while (I%2 == 0){
      I /= 2;
      c++;
    }
    if (max < c){
      max = c;
      answer = i;
    }
  }
    
    cout << answer << endl;
   
}

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

typedef pair<int,int> pii;
int dptab[256][1024] = {0};

int main() {
	int n, m;
	while(cin >> n, n) {
		vector<pii> v;
		for(int i = 0; i < n; i++) {
			pii tmp;
			cin >> tmp.first >> tmp.second;
			v.push_back(tmp);
		}
		cin >> m;
		for(int i = 0; i < m; i++) {
			pii tmp;
			cin >> tmp.first >> tmp.second;
			v.push_back(tmp);
		}
		sort(v.begin(), v.end());

		for(int i = 0; i < 256; i++)
			for(int j = 0; j < 1024; j++)
				dptab[i][j] = 0;

		for(int i = 0; i < v.size(); i++) {
			for(int j = 0; j < 1024; j++) {
				if(i > 0 && v[i].first == v[i - 1].first) {
					dptab[i + 1][j]
						= max(dptab[i][j], v[i].second < j ? dptab[i - 1][v[i].second] + 1 : 0);
				}
				else {
					dptab[i + 1][j]
						= max(dptab[i][j], v[i].second < j ? dptab[i][v[i].second] + 1 : 0);
				}
			}
		}
		cout << dptab[n + m][1010] << endl;
	}
}

Measured memory_bytes: 2228
x1, x2, x3, x4, x5 = input().split()
x = list()
x.append(x1)
x.append(x2)
x.append(x3)
x.append(x4)
x.append(x5)
ans = 0
for i, j in enumerate(x):
  if int(j) == 0:
  	ans = i+1
print(int(ans))


Measured memory_bytes: 9056
#include <algorithm>
#include <vector>
#include <map>
#include <iostream>
#include <string>

typedef long long ll;

using namespace std;
int main()
{

	int N;
	string s;

	
	cin >> N >> s;

	int r = 0;
	int b = 0;

	for (char c : s)
	{
		if (c == 'R')
			r++;
		else
			b++;

	}

	if (r > b)
		cout << "Yes";
	else
		cout << "No";
	
	return 0;
}


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

using namespace std;

#define loop(i,a,b) for(int i=(a); i<(b); i++)
#define rep(i,b) loop(i,0,b)

int main(){
    int n;
    while(cin >> n && n){
        int a[15];
        rep(i,n) cin >> a[i];
        int c = 0;
        while(1){
            map<int,int> m;
            rep(i,n) m[a[i]]++;
            bool up = false;
            rep(i,n){
                if(a[i] != m[a[i]]){
                    a[i] = m[a[i]];
                    up = true;
                }
            }
            if(!up) break;
            else c++;
        }
        cout << c << endl;
        rep(i,n) cout<<a[i]<<(i==n-1 ? "\n" : " ");
    }
}

Measured memory_bytes: 1196
#define REP(i, n) for(int i = 0;i < n;i++)
#define INF 2e9
#define ll long long
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ALL(v) v.begin(), v.end()

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;

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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S; cin >> S;
    int c = 0, max = 0;
    REP(i, S.size()) {
        if (S.at(i) == 'A' or S.at(i) == 'C' or S.at(i) == 'G' or S.at(i) == 'T') {
            c++;
        } else {
            if (c > max) max = c;
            c = 0;
        }
    }
    if (c > max) max = c;
    cout << max << endl;
}



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

// Problem https://atcoder.jp/contests/abc071/tasks/abc071_b

// 26と限定されているのでバケット法を使う
// 要文字コード
char solver(string inputString){
    char result;
    int resultInt;
    vector<int> charCount(26,0);
    for(int j=0;j<inputString.size();j++){
        charCount.at(inputString.at(j)-97)=charCount.at(inputString.at(j)-97)+1;
    }
    // 結果判定
    bool allCheckFlg = true;
    for(int j=0;j<26;j++){
        if(charCount.at(j)==0){
            allCheckFlg = false;
            resultInt = j;
            break;
        }
    }

    if(allCheckFlg){
        result = 'X';
    }
    else{
        result = resultInt + 97;
    }
    return result;
}

int main(void){
    char answer;
    string S;
    cin >> S ;
    answer = solver(S);
    if(answer == 'X'){
        cout << "None" << endl;
        return 0;
    }
    cout << answer << endl;
    return 0;
}


Measured memory_bytes: 512
N = int(input())
# n, *a = map(int, open(0))
# M, D = map(int, input().split())
D = list(map(int, input().split()))
# S = input()
cnt = 0
import itertools
l = list(itertools.combinations(D,2))
for t in l:
    cnt += t[0] * t[1]
print(cnt)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < n; ++i)
#define P pair<ll, ll>
#define Graph vector<vector<ll>>
#define fi first
#define se second
constexpr ll mod = 1000000007;
constexpr ll INF = (1ll << 60);
constexpr double pi = 3.14159265358979323846;
template <typename T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}

int main() {
    ll a, b;
    cin >> a >> b;
    cout << (a + b + 1) / 2 << "\n";
    return 0;
}

Measured memory_bytes: 3512
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
  ll n;
  cin>>n;
  ll k;
  for(ll i=1;i*i<=n;i++)
  {
    if(n%i==0)
      k=i;
  }
  cout<<(k-1)+(n/k-1);
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <numeric>
#include <cmath>
using namespace std;
//変数デバッグ
#define DEB(variable) cout << #variable << '=' << variable << endl

//for簡易表記(引数ミス防止)
#define FOR(LoopVariable,numberOFbegin,numberOFend) for (int LoopVariable = (numberOFbegin); (LoopVariable) < (numberOFend); (LoopVariable)++)
#define REP(LoopVariable,numberOFend) for(int LoopVariable = 0;(LoopVariable)<(numberOFend);LoopVariable++)


int main(){

    long long int n, x;
    cin >> n >> x;
    long long int result=0,finder=0;
    bool upperflag = 1;
    for (int i = n+1 ; i > 0;i--){
        finder += ((!upperflag)*(-1)+(upperflag))*((long long int)pow(2, i) - 1);
        if(x==finder){
            result += (long long int)pow(2, i-1);
            break;
        }else if(x>finder){
            upperflag = true;
            result += (long long int)pow(2, i-1);
        }else{
            upperflag = false;
        }
    }
    cout << result << endl;
    return 0;
}

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

vector<int> parallel[1080];
int h, p, q, n, m, a;

bool solve(){
	cin >> n >> m >> a;
	if(n == 0 && m == 0 && a == 0)return false;
	for(int i = 1;i <= 1000;i++)parallel[i].clear();
	for(int i = 0;i < m;i++){
		cin >> h >> p >> q;
		parallel[h].push_back(p);
	}

	for(int i = 1000;i >= 0;i--){
		for(int j = 0;j < parallel[i].size();j++){
			int p = parallel[i][j];
			int q = p + 1;
			if(a == p)a = q;
			else if(a == q)a = p;
			
		}
	}
	cout << a << endl;
	return true;
}

int main(){
	while(solve());
	return 0;
}

Measured memory_bytes: 3204
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i=0;i<((int)(n));i++)
#define reg(i,a,b) for(int i=((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i=((int)(n))-1;i>=0;i--)
#define ireg(i,a,b) for(int i=((int)(b));i>=((int)(a));i--)
typedef long long int lli;
typedef pair<int,int> mp;
#define fir first
#define sec second
#define IINF INT_MAX
#define LINF LLONG_MAX
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define pque(type) priority_queue<type,vector<type>,greater<type> >
#define memst(a,b) memset(a,b,sizeof(a))
#define iter(v,ite) for(auto ite=(v).begin();ite!=(v).end();ite++)


set<int> vs[40005];
set<int> nv[40005];


int ps[40005];
void dfs(int no,int g){
	if(ps[no]!=-1)return;
	ps[no]=g;
	iter(nv[no],ite){
		if(ps[*ite]!=-1)continue;
		dfs(*ite,g);
	}
}


map<int,int> vm[40005];
void adde(int a,int b){
	if(a==b)return;
	if(vm[a].count(b))vm[a][b]++;
	else vm[a][b]=1;
}

void rmve(int a,int b){
	if(a==b)return;
	vm[a][b]--;
}

int gone[40005];
bool dfm(int no,int q){
	//printf("dfm %d %d\n",no,q);
	gone[no]=1;
	if(no==q)return true;
	iter(vm[no],ite){
		mp pa = (*ite);
		if(pa.sec==0)continue;
		int to=pa.fir;
		if(gone[to])continue;
		if(dfm(to,q))return true;
	}
	return false;
}

typedef pair<int,mp> mmp;
int n,k;
int main(void){
	scanf("%d%d",&n,&k);
	int sq = sqrt(k);
	int r = k-(sq*sq);
	rep(qqq,sq){
		int nk = sq;
		if(r>qqq)nk++;
		if(r-sq>qqq)nk++;
		//printf("roop: %d %d\n",qqq,nk);
		vector<mmp> dat;
		rep(i,n)nv[i]=set<int>(vs[i]);
		
		rep(i,nk){
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			dat.push_back(mmp(a,mp(b,c)));
			if(a==2){
				if(nv[b].count(c))nv[b].erase(c);
				if(nv[c].count(b))nv[c].erase(b);
			}
		}
		memset(ps,-1,sizeof(ps));
		rep(i,n){
			if(ps[i]!=-1)continue;
			dfs(i,i);
		}
		//rep(i,n)printf("ps %d %d\n",i,ps[i]);
		
		rep(i,n)vm[i].clear();
		rep(i,n){
			int a = ps[i];
			iter(vs[i],ite){
				int b=ps[*ite];
				adde(a,b);
			}
		}
		
		rep(i,nk){
			int a = dat[i].fir,
				b = dat[i].sec.fir,
				c = dat[i].sec.sec;
			
			if(a==1){
				vs[b].insert(c);
				vs[c].insert(b);
			}
			else if(a==2){
				vs[b].erase(c);
				vs[c].erase(b);
			}
		}

		
		rep(i,nk){
			/*
			printf("turn %d\n",i);
			rep(i,n)iter(vm[i],ite){
				printf("map %d : %d %d\n",i,(*ite).fir,(*ite).sec);
			}
			*/
				
			mmp pa = dat[i];
			int t = pa.fir,
				a = pa.sec.fir,
				b = pa.sec.sec;
			a = ps[a]; b = ps[b];
			if(t==1){
				adde(a,b);
				adde(b,a);
			}
			else if(t==2){
				rmve(a,b);
				rmve(b,a);
			}
			else{
				memset(gone,0,sizeof(gone));
				printf("%s\n",dfm(a,b)?"YES":"NO");
			}
		}
	}
	return 0;
}

Measured memory_bytes: 15840
n,m=map(int,input().split())
L=1
R=n
for i in range(m):
  l,r=map(int,input().split())
  L=max(l,L)
  R=min(r,R)

if (R-L+1)>=0:
  print(R-L+1)
else:
  print(0)

Measured memory_bytes: 3060
#include <stdio.h>

int main(void){
    
    int H=1;
    int Y=1;
    int i,j;
    
    
    
    if(H>=300 && Y>=300){
        return 0;
    }
    
    while(H != 0 && Y != 0){
        scanf("%d %d",&H,&Y);
        
        for(i=0;i<H;i++){
            if(i%2==0){
                for(j=0;j<Y;j++){
                    if(j%2==0){
                        printf("#");
                    }else{
                        printf(".");
                    }
                }
                printf("\n");
            }else{
                for(j=0;j<Y;j++){
                    if(j%2==0){
                        printf(".");
                    }else{
                        printf("#");
                    }
                    
            }
                printf("\n");
        }
        
    }
        if(H != 0 && Y != 0)
        printf("\n");
    }
    return 0;
}

Measured memory_bytes: 572
fn main() {
    let (n, x, d) = {
        let mut buf = String::new();
        std::io::stdin().read_line(&mut buf).unwrap();
        let mut iter = buf.split_whitespace();
        (
            iter.next().unwrap().parse::<usize>().unwrap(),
            iter.next().unwrap().parse::<i64>().unwrap(),
            iter.next().unwrap().parse::<i64>().unwrap(),
        )
    };

    if d == 0 {
        if x == 0 {
            println!("1");
        } else {
            println!("{}", n + 1);
        }
        return;
    }

    let x = if d < 0 { -x } else { x };
    let d = if d < 0 { -d } else { d };

    let mut map = std::collections::HashMap::new();
    for k in 0..=n {
        let n = n as i64;
        let k = k as i64;
        let key = k * x % d;
        let range = {
            [
                k * x + (k - 1) * k / 2 * d,
                k * x + ((n - k) + (n - 1)) * k / 2 * d,
            ]
        };
        (*map.entry(key).or_insert(Vec::new())).push(range);
    }

    let mut ans = 0;
    for value in map.values_mut() {
        value.sort();
        ans -= 1;
        let mut left = std::i64::MIN;
        let mut right = std::i64::MIN;
        for range in value {
            if range[0] <= right {
                right = std::cmp::max(right, range[1]);
            } else {
                ans += (right - left) / d + 1;
                left = range[0];
                right = range[1];
            }
        }
        ans += (right - left) / d + 1;
    }
    println!("{}", ans);
}

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

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

const long long INF = 1LL << 60;

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];

  ll total = 1000;
  rep(i, n-1){
    if(a[i] <= a[i+1]){
      total += (a[i+1]-a[i]) * (total/a[i]);
    }
  }

  cout << total << endl;

  return 0;
}


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

using namespace std;
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){os << "["; for (const auto &v : vec) {os << v << ","; } os << "]"; return os; }
template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) {os << "(" << p.first << ", " << p.second << ")"; return os;}

int get(int rate) {
    if (rate < 400) return 0;
    else if (rate < 800) return 1;
    else if (rate < 1200) return 2;
    else if (rate < 1600) return 3;
    else if (rate < 2000) return 4;
    else if (rate < 2400) return 5;
    else if (rate < 2800) return 6;
    else if (rate < 3200) return 7;
    return 8;
}

void solve() {
    int N;
    cin >> N;
    vector<int> A(N);

    int pro = 0;
    set<int> C;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        if (get(A[i]) == 8) {
            pro++;
        } else {
            C.insert(get(A[i]));
        }
    }

    if (!pro) {
        cout << C.size() << " " << C.size() << endl;
    } else {
        if (C.size() == 0) {
            cout << 1 << " " << pro << endl;
        } else {
            cout << C.size() << " " << C.size() + pro << endl;
        }
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}

Measured memory_bytes: 256
// 物极必反

#include <bits/stdc++.h>

#define append push_back

using namespace std;
using ll = long long;

const int N = 2e5 + 3;
const int M = 2e6 + 7;
const long long MOD = 1e9 + 7;
const long long INF = 1e18 + 9;
const int SM = 3e3 + 5;
const int logN = 22, BL = 400;
const double EPS = 1e-9;
const double PI = acos(-1);
const int dx[] = {1, 0, 0, -1, -1, 1, -1, 1};
const int dy[] = {0, 1, -1, 0, -1, 1, 1, -1};

void debug(){
	cerr << "\n";
}
template<typename Type1, typename... Type2>
void debug(Type1 a, Type2... b) {
    cerr << a << " ";
    debug(b...);
}

int main(){
//    freopen(".in", "r", stdin);
//    freopen(".out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    string s, t; cin >> s >> t;

    long long cnt = 0;
    for(long long i = 0; i < s.size(); i++){
        cnt += s[i] != t[i];
    }

    cout << cnt;
    return 0;
}


Measured memory_bytes: 3804
import sys
buf = sys.stdin.buffer

import numpy as np
MOD = 10 ** 9 + 7

H,W = map(int,buf.readline().split())

grid = np.frombuffer(buf.read(),dtype='S1').reshape(H,-1)[:,:W]

MOD = 10 ** 9 + 7
dp = np.zeros(W, dtype=np.int64)
dp[0] = 1
for row in grid:
    wall = (row == b'#')
    # 上から落としてくる
    dp[wall] = 0
    # 左から右に
    np.cumsum(dp, out = dp)
    # 壁の補正
    sub = np.maximum.accumulate(dp * wall)
    dp -= sub
    dp %= MOD

answer = dp[-1]
print(answer)

Measured memory_bytes: 14408
package main

import (
	"fmt"
	"strconv"
)

func main() {
	var n, b, f, r, v int
	var ans [4][3][10]int

	fmt.Scan(&n)

	for i := 0; i < n; i++ {
		fmt.Scan(&b, &f, &r, &v)
		ans[b - 1][f - 1][r - 1] += v
	}

	for i := 0; i < 4; i++ {
		for j := 0; j < 3; j++ {
			tmp := ""
			for k := 0; k < 10; k++ {
				tmp += " " + strconv.Itoa(ans[i][j][k])
			}
			fmt.Println(tmp)
		}
		
		if i != 3 {
			fmt.Println("####################")
		}
	}
}


Measured memory_bytes: 1132
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
int main(){
	int n;
	while(cin>>n){
		if(!n)break;
		vector<pair<int,int> > t;
		while(n--){
			int m,a,b;
			cin>>m>>a>>b;
			t.push_back(make_pair<int,int>(b,-m));
			t.push_back(make_pair<int,int>(a,m));
		}
		stable_sort(t.begin(), t.end());
		int sum=0,ng=0;
		for(vector<pair<int,int> >::iterator it=t.begin();it!=t.end();++it){
			sum+=(*it).second;
			if(sum>150)ng=1;
		}
		cout<<((ng)?"NG\n":"OK\n");
	}
	return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<cstring>
#include<stack>
#include<functional>
using namespace std;
#define int long long

struct Bug{
	int out,in;
	bool operator <(const Bug &a)const{
		return in>a.in;
	}
};

int N;
Bug b[300000];

bool isTokyo(int k){
	multiset<int> latte;
	int sum = 0;
	for(int i=0;i<N;i++){
		if(latte.size()<k-1){
			sum += b[i].out; latte.insert(b[i].out); continue;
		}
		if((double)(sum+b[i].out)/(double)k<=(double)b[i].in) return true;
		if(latte.size()==0) continue;
		multiset<int>::iterator max_ = latte.end(); max_--;
		if(*max_>b[i].out){
			sum -= *max_;
			latte.erase(max_);
			sum += b[i].out;
			latte.insert(b[i].out);
		}
	}
	return false;
}

signed main(){
	cin>>N;
	for(int i=0;i<N;i++) cin>>b[i].out>>b[i].in;
	sort(b,b+N);
	int l=0, r=N+1;
	while(l+1 != r){
		int piv = (l+r)/2;
		if(isTokyo(piv)) l = piv;
		else r = piv;
	}
	printf("%d\n",l);
	return 0;
}

Measured memory_bytes: 19812
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, ans;
  cin >> n;
  
  vector<int> b(n - 1);
  for(int i = 0; i < n - 1; i++){
    cin >> b.at(i);
  }
  
  ans = b.at(0);
  
  for(int i = 1; i < n - 1; i++)
    ans += min(b.at(i - 1), b.at(i));

  if(n > 1)
    ans += b.at(n - 2);
  
  cout << ans << "\n";
  
  return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil
from operator import itemgetter
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
inf = 10**17
mod = 10**9 + 7

#s=input().rstrip()
n=I()
h=LI()
plus=[]
minus=[]
for i in range(1,n+1):
    plus.append(i+h[i-1])
    minus.append(i-h[i-1])
#print(plus)
#print(minus)

ans=0
c=Counter(plus)
for m in minus:
    ans+=c[m]
print(ans)

Measured memory_bytes: 51264