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

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
using ii=pair<int,int>;

const int mxN = 2e5+5;

int N, A[mxN];
ii stk[mxN]; int tp;

inline bool check(int C) {
    if (C == 0) return 0;
    stk[0] = ii(0,0); tp = 1;
    A[0] = 0;
    FOR(i,1,N){
        if (A[i] > A[i-1]) {
            stk[tp++] = ii(A[i],0);
        } else {
            while (tp > 1 && stk[tp-2].first >= A[i]) --tp;
            stk[tp-1].first = A[i];
            RFOR(j,tp-1,0){
                if (j == 0) return 0;
                if (++stk[j].second == C) {
                    stk[j].second = 0;
                } else {
                    if (stk[j-1].first+1 < stk[j].first) {
                        RFOR(k,tp-1,j) stk[k+1] = stk[k];
                        ++tp;
                        stk[j] = ii(stk[j+1].first-1,stk[j+1].second-1);
                    }
                    break;
                }
            }
        }
        //cout << i << " :: ";
        //FOR(j,0,tp-1) cout << stk[j].first << ", " << stk[j].second << " | ";
        //cout << endl;
    }
    return 1;
}

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

    cin >> N;
    FOR(i,1,N){
        cin >> A[i];
    }

    int lo = 0, hi = N;
    while (hi-lo > 1) {
        int mid = (lo+hi)/2;
        if (check(mid)) hi = mid;
        else lo = mid;
    }
    cout << hi << '\n';
}



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

using namespace std;

int main()
{
  string S;
  cin >> S;
  if (S == "zyxwvutsrqponmlkjihgfedcba")
    cout << -1 << endl;
  else if (S.size() == 26)
  {
    string tmp = S;
    next_permutation(tmp.begin(), tmp.end());
    for (int i = 0; i < 26; i++)
    {
      cout << tmp[i];
      if (S[i] != tmp[i])
        break;
    }
    cout << endl;
  }
  else
  {
    bool use[26] = {};
    for (int i = 0; i < S.size(); i++)
      use[S[i] - 'a'] = true;
    for (int i = 0; i < 26; i++)
      if (!use[i])
      {
        cout << S << (char)('a' + i) << endl;
        break;
      }
  }

  return 0;
}


Measured memory_bytes: 256
// AtCoder AGC041 A - Table Tennis Training
// 2020.1.22 bal4u

#include <stdio.h>

typedef long long ll;
ll MIN(ll a, ll b) { return a <= b? a: b; }
ll calc(ll A, ll B) { return A+(B-A-1)/2; }

int main()
{
	ll N, A, B, ans;
	scanf("%lld%lld%lld", &N, &A, &B);
	if ((B-A) % 2 == 0) ans = (B-A)/2;
	else ans = MIN(calc(A, B), calc(N-B+1, N-A+1));
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int gcd(int p, int q)
{
  if (p%q == 0) return q;
  return gcd(q, p%q);
}

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

  int ans = 0;
  for (int i = 1; i <= K; ++i)
  {
    for (int j = 1; j <= K; ++j)
    {
      for (int p = 1; p <= K; ++p)
      {
        ans += gcd(i, gcd(j, p));
      }
     }
  }
  cout << ans << endl;
}

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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << fixed << setprecision(15);

  int a, b;
  cin >> a >> b;

  string ans;
  if (a == 0 || b == 0) {
    ans = "Zero";
  } else if (a < 0 && 0 < b) {
    ans = "Zero";
  } else if (0 < a) {
    ans = "Positive";
  } else {
    if ((b - a) % 2 == 0) {
      ans = "Negative";
    } else {
      ans = "Positive";
    }
  }
  cout << ans << '\n';

  return 0;
}


Measured memory_bytes: 3644
import numpy as np
n = int(input())
m = int(np.log10(n))
ans = 0

for i in range(m+1):
    if m%2 == 1:
        n = 10**m - 1
        m -= 1
    else:
        ans += n - 10**m + 1 
        n = 10**m - 1
        m -= 1

print(ans)

Measured memory_bytes: 21800
N = int(input())
blue = [input() for _ in range(N)]
M = int(input())
red = [input() for _ in range(M)]

ans = 0
for s in blue[:]:
    if blue.count(s) - red.count(s) > ans:
        ans = blue.count(s) - red.count(s)
print(ans)

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

typedef long long ll;
typedef unsigned long long ull;
#define fr first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()

using namespace std;

const ll MOD = 1000000007;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;
    int ac = 0, wa = 0, tle = 0, re = 0;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        if (s == "AC")
            ac++;
        else if (s == "WA")
            wa++;
        else if (s == "TLE")
            tle++;
        else
            re++;
    }
    cout << "AC x " << ac << endl;
    cout << "WA x " << wa << endl;
    cout << "TLE x " << tle << endl;
    cout << "RE x " << re;

    return 0;
}


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

int main(){
    int n, w;
    cin >> n >> w;
    int V[n], W[n];
    for(int i = 0; i < n; i++){
        cin >> V[i] >> W[i];
    }

    int dp[n + 1][w + 1];
    for(int i = 0; i <= w; i++){
        dp[0][i] = 0;   //0個選んだ時の重さは0(それはそう)
    }
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= w; j++){
            if(j >= W[i]){
                dp[i + 1][j] = max(dp[i][j], dp[i][j - W[i]] + V[i]);
                /*
                if(dp[i + 1][j] == dp[i][j - W[i]] + V[i]){
                    cout << "aa " << i + 1 << " " << j << " " << dp[i + 1][j] << endl;
                }
                */
            }else{
                dp[i + 1][j] = dp[i][j];   //MAXまで重さきてるから入れられないため更新無し（今までの最大値流用）
            }
        }
    }
    cout << dp[n][w] << endl;


    return 0;
}


Measured memory_bytes: 7036
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdlib>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <functional>
#include <vector>
#include <iterator>
#define ll long long
#define Lu unsigned long long

const int inf = 0x3f3f3f3f3f;
const int maxn = 1e5 + 50;

using namespace std;

Lu A[maxn];
bool vis[maxn];

int main()
{
    int N;
    scanf("%d",&N);
    for(int i=0;i<N;i++)
        scanf("%llu",&A[i]);

    sort(A,A+N);
    Lu a=0,b=0;
    int flaga=0,flagb=0;

    for(int i=N-2;i>=0;i--)
    {
        if(A[i] == A[i+1] && !flaga && !vis[i] && !vis[i+1])
            a = A[i],flaga=1,vis[i]=vis[i+1] = 1;
        if(flaga && !flagb &&A[i] == A[i+1] && !vis[i] && !vis[i+1])
            b = A[i],flagb=1,vis[i] = vis[i+1] = 1;
        if(flaga && flagb)
            break;
    }
    printf("%llu",a*b);
    return 0;
}


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

int main()
{
    ll n,d,cnt=0;
    cin>>n>>d;
    while(n--)
    {
        ll x,y;
        cin>>x>>y;
        x=abs(x);
        y=abs(y);
        if(x*x+y*y<=d*d)
            cnt++;
    }
    cout<<cnt<<endl;

}


Measured memory_bytes: 3628
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <string>
#include <cmath>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i,i0,n) for(int (i)=(i0);(i)<(n);(i)++)
#define rn return
typedef std::pair<int,int> P;
using namespace std;
using ll = long long;



int main(){
    vector<int> ABC(3);
    rep(i,3) cin >> ABC[i];
    sort(ABC.begin(),ABC.end());
    cout << ABC[0] + ABC[1] + ABC[2]*10;
}


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

typedef long long ll;
typedef long double ld;
#define pi 3.14159265359
#define inf 2147483647
#define INF 9223372036854775807
#define mod 1000000007
#define mod2 998244353

int main() {
    vector<string> S(3);
    for (int i = 0; i < 3; i++) {
        cin >> S.at(i);
    }
    sort(S.begin(), S.end());
    string x = S.at(2) + S.at(1), y = S.at(0);
    int ans = stoi(x) + stoi(y);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
X = int(input())
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
data = primes(2*X)
for i in range(len(data)):
    if data[i] >= X:
        ans = data[i]
        break
print(ans)

Measured memory_bytes: 5260
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

using pi = pair<int,int>;
using P = pair<int,pi>;

struct edge{int to,cost,time,company;};

const int V=100;
const int INF=123456789;

vector<edge> G[V];

int dp[300];
int d[100][25];

int main()
{
    int N,M,H,K;
    while(scanf(" %d %d %d %d", &N, &M, &H, &K),N)
    {
        rep(i,V) G[i].clear();

        rep(i,M)
        {
            int a,b,c,h,r;
            scanf(" %d %d %d %d %d", &a, &b, &c, &h, &r);
            --a;
            --b;
            --r;
            G[a].pb({b,c,h,r});
            G[b].pb({a,c,h,r});
        }

        int S,T;
        scanf(" %d %d", &S, &T);
        --S;
        --T;

        int PASS;
        scanf(" %d", &PASS);

        vector<int> pass_cost(PASS),mask(PASS);
        rep(i,PASS)
        {
            int l;
            scanf(" %d %d", &l, &pass_cost[i]);

            rep(j,l)
            {
                int k;
                scanf(" %d", &k);
                --k;

                mask[i] |= 1<<k;
            }
        }

        fill(dp,dp+300,INF);
        dp[0]=0;
        rep(i,1<<K)rep(j,PASS)
        {
            int nx = i|mask[j];
            dp[nx] = min(dp[nx],dp[i]+pass_cost[j]);
        }

        int ans=INF;
        rep(i,1<<K)
        {
            if(dp[i]==INF) continue;
            
            fill(d[0],d[100],INF);
            d[S][0]=0;

            priority_queue<P,vector<P>,greater<P>> pq;
            pq.push(P(0,pi(S,0)));
            while(!pq.empty())
            {
                P now = pq.top();
                pq.pop();

                int v = now.se.fi, h = now.se.se;
                if(now.fi>d[v][h]) continue;

                for(const auto &e:G[v])
                {
                    int nh = h+e.time;
                    if(nh>H) continue;

                    int COST = e.cost;
                    if(i>>e.company&1) COST = 0;

                    if(d[e.to][nh] > d[v][h]+COST)
                    {
                        d[e.to][nh] = d[v][h]+COST;
                        pq.push(P(d[e.to][nh],pi(e.to,nh)));
                    }
                }
            }

            rep(j,H+1) ans = min(ans,d[T][j]+dp[i]);
        }

        if(ans==INF) ans=-1;
        printf("%d\n", ans);
    }
    return 0;
}

Measured memory_bytes: 3400
h, w = map(int, input().split())
A = []
A.append(['.'] * (w+2))
for i in range(h):
    A.append(list('.' + input() + '.'))
A.append(['.'] * (w+2))

ans = 'Yes'
for i in range(1, h+1):
    for j in range(1, w+1):
        if A[i][j] == '#':
            if A[i+1][j] == '#' or A[i-1][j] == '#' or A[i][j+1] == '#' or A[i][j-1] == '#':
                continue
            else:
                ans = 'No'

print(ans)

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = Integer.parseInt(sc.next());
		String S = sc.next();
		String T = sc.next();
		sc.close();

		StringBuffer sb = new StringBuffer();
		for(int i = 0; i < N; i++) {
			char tmpS = S.charAt(i);
			sb.append(tmpS);
			char tmpT = T.charAt(i);
			sb.append(tmpT);
		}
		String ans = sb.toString();
		System.out.println(ans);

	}

}

Measured memory_bytes: 21588
#include<bits/stdc++.h>
#define ll long long
#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }


using namespace std;

int main() {
    ll n;
    cin >> n;

    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    multiset<ll> s;

    for (ll i = 0; i < n; ++i) {
        ll now = a[i];
        auto itr = s.lower_bound(now);
        if (itr != s.begin()) s.erase(--itr);
        s.insert(now);
    }

    cout << s.size() << endl;

}


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

int main() {

    int m, d;
    cin >> m >> d;
    
    int count = 0; 
    for(int i = 0; i < m; ++i){
        
        for(int j = 21; j < d; ++j){
            if((j+1)-(((j+1)/10)*10) >= 2 && ((j+1)-(((j+1)/10)*10))*((j+1)/10) == i+1){
                ++count;
            }
    
        }
    }

    cout << count << endl;

}

Measured memory_bytes: 256
//#define LOCAL

#include <fstream>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <climits>
#include <set>

//#define int long long
typedef long long ll;
//#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)

#define MOD 1000000007

using namespace std;

typedef vector<int> V;
typedef vector<V> VV;

ll F(ll A, ll B)
{
    return max(log10(A) + 1, log10(B) + 1);
}

signed main()
{
#ifdef LOCAL
    ifstream in("input.txt");
    cin.rdbuf(in.rdbuf());
#endif

    ll N;
    ll ans = LONG_LONG_MAX;

    cin >> N;
    for (ll i=1; i*i<=N; i++) {
        if (N % i == 0) {
            ans = min(ans, F(i, N / i));
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 512
object Main extends App {
    val List(amount: Int, countOfdislikeWord: Int) = readLine.split(" ").toList.map(_.toInt)
    val listOfDislikeWord = readLine.split(" ").toList.map(_.toInt)
    val answer = (amount to (10*amount)).find(p => p >= amount && !isContainsLikeNumber(listOfDislikeWord, p))
    println(answer.get)

    def isContainsLikeNumber(listOfDislikeWord: List[Int], amount: Int): Boolean = {
      // 合計金額を桁ごとにListにしたもの
      val amountList = amount.toString.toList.map(_.asDigit)
      amountList.exists(p => listOfDislikeWord.contains(p))
    }
}


Measured memory_bytes: 38956
#include <stdio.h>

void swap(int*, int*);

int main(void) {
	int i, j;
	int height[10];
	
	for (i = 0; i <= 9; i++)
		scanf("%d", &height[i]);
	
	for (i = 9; i > 0; i--)
		for (j = 0; j < i; j++)
			if (height[j] < height[j + 1])
				swap(&height[j], &height[j + 1]);

	for (i = 0; i < 3; i++)
		printf("%d\n", height[i]);
	return 0;
}

void swap(int *a, int *b) {
	int c;
	c = *a;
	*a = *b;
	*b = c;
}

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

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

    int num = 0;

    if (b == 100) num = a * 1000 + b;
    if (10 <= b && b < 100) num = a * 100 + b;
    if (b < 10) num = a * 10 + b;

    int s = sqrt(num);
    if ( num == s * s) cout << "Yes" << endl;
    else cout << "No" << endl;





    return 0;
    
}

Measured memory_bytes: 256
N,M=map(int,input().split())
ab_dic={}
for i in range(N):
    a,b=list(map(int, input().split()))
    if a in ab_dic.keys():
        ab_dic[a]+=b
    else:
        ab_dic[a]=b

ab_dic=sorted(ab_dic.items())
want=M
cout=0
money=0

while want>0:
    if ab_dic[cout][1]<want:
        money+=ab_dic[cout][0]*ab_dic[cout][1]
        want-=ab_dic[cout][1]
    else:
        money+=ab_dic[cout][0]*want
        break
    cout+=1
print(money)

Measured memory_bytes: 23004
N=int(input())

L1=2
L2=1

for i in range(1,N,2):
    L3=L1+L2
    L4=L2+L3
    L1=L3
    L2=L4
if(N==1):
    print("1")
elif(N%2==0):
    print(L3)
else:
    print(L4)


Measured memory_bytes: 2940
def main():
    N=int(input())
    s=input()
    ind=[[0 for j in range(10)] for i in range(N)]
    first=[-1 for i in range(10)]
    last=[-1 for i in range(10)]

    k=int(s[0])
    first[k]=0
    last[k]=0
    ind[0][k]=1

    for i in range(1,len(s)):
        k=int(s[i])
        if first[k]==-1: first[k]=i
        last[k]=i
        ind[i]=[ind[i-1][j] for j in range(10)]
        ind[i][k]=ind[i-1][k]+1

    ans=0
    for i in range(10):
        for j in range(10):
            f=first[i]
            l=last[j]
            if f!=-1 and f+1<l:
                for k in range(0,10):
                    if ind[f][k]<ind[l-1][k]: ans+=1
                    

    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 10340
#include <iostream>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <stack>
#include <list>
#include <utility>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <climits>
#include <map>
#include <unordered_map>
#include <string.h>
#include<iomanip>
#include <iterator>
#include <locale>

#define all(a) a.begin(),a.end()
#define VV(T) vector<vector< T > >
#define rep(i,N) for(int i = 0; i <N; i++)
#define repsg(i,s,g) for(int i = s; i <g; i++)
#define name(x) #x
using namespace std;


const int INF = 10000000;
const long long INFL = (1LL<<40);
const int MOD = pow(10,9)+7;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

typedef long long ll,LL;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
typedef pair<int,int> pii;
typedef pair<LL, LL> pLL;


// vector入力
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
    for(T& x: vec) is >> x;
    return is;
}
// vector出力
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec){
    for(int i=0; i<vec.size(); i++){
        os << vec[i] << ( i+1 == vec.size() ? "" : " " );
    }
    return os;
}

template< typename T >
struct edge{
    int src, to;T cost;
    edge(int to,T cost) :src(-1),to(to),cost(cost){}
    edge(int src, int to, T cost) :src(src),to(to),cost(cost){}edge
    &operator=(const int &x){
        to =x;
        return *this;
    }
    operator int() const{ return to;}
};

double dist (double a, double b,  double c, double d){
    
    return sqrt((a-c)*(a-c) + (b-d)*(b-d));
    
}

bool check(int x,int y,vector<string> a,vector<string> b ){
    for(auto i = 0; i<b.size();i++){
        for(auto j =0; j<b.size();j++){
            if(a[x+i][y+j]!= b[i][j]) return false;
        }
    }
    return true;
}

int dist(pii a, pii b){
    return abs(a.first-b.first) + abs(a.second-b.second);
}

int main() {
    int n,m;cin>>n>>m;
    int c[51]={0};
    int a,b;
    rep(i,m){
        cin>>a>>b;
        c[a-1]++;
        c[b-1]++;
    }
    for(auto i =0;i<n;i++){
        cout<<c[i]<<endl;
    }
    
    return 0;
}







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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
using P = pair<ll, ll>;
using V = vector<ll>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep1(i, n) for(ll i=1;i<=(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
#define ALL(obj) (obj).begin(), (obj).end()
#define RALL(obj) (obj).rbegin(), (obj).rend()
#define MOD 1000000007
#define INF 1000000000
#define LLINF 1e18

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

void solve_abc_a() {
	ll n, m;
	ll x, y;
	ll a, b, d;
	ll c;
	//char c;
	ll h, w;
	ll k;
	string s, t;
	//ll s, t;
	ll l_ans = 0;
	string s_ans = "NG";

	cin >> n;

	vector<P> di(n);
	ll cnt = 0;
	s_ans = "No";
	rep(i, n) {
		cin >> di[i].first >> di[i].second;
	}

	rep(i, n) {
		if (di[i].first == di[i].second) {
			cnt++;
			if (cnt >= 3) {
				s_ans = "Yes";
				break;
			}
		}
		else {
			cnt = 0;
		}
	}

	cout << s_ans << "\n";

	return;
}


int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed;
	cout << setprecision(7);

	solve_abc_a();

	return 0;
}


Measured memory_bytes: 3652
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
#define chmin(a, b) ((a) = min((a), (b)))
#define chmax(a, b) ((a) = max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

const ll MOD = 1e9 + 7;
const ll INF = 1e18;
const double pi = acos(-1);
const double eps = 1e-10;

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

int main(){
    int n, m; cin>>n>>m;
    vector<vector<int>> imos(n+10, vector<int>(n+10, 0));
    for(int i=0; i<m; i++){
        int a, b, x; cin>>a>>b>>x;
        imos[a][b]++;
        imos[a][b+1]--;
        imos[a+x+1][b]--;
        imos[a+x+1][b+x+2]++;
        imos[a+x+2][b+1]++;
        imos[a+x+2][b+x+2]--;
    }

    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            imos[i][j+1] += imos[i][j];
        }
    }

    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            imos[j+1][i] += imos[j][i];
        }
    }

    for(int i=1; i<=n; i++){
        int cnt = 0;
        for(int j=1; j<=n-i+1; j++){
            imos[i+1+cnt][j+1] += imos[i+cnt][j];
            cnt++;
        }
    }

    int ans = 0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(0 < imos[i][j]) ans++;
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 101084
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

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

    static class B {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            // 入力
            int n = Integer.parseInt(in.next());
            int d = Integer.parseInt(in.next());

            int ans = 0;
            if (n % (2 * d + 1) == 0) {
                ans = n / (2 * d + 1);

            } else {
                ans = n / (2 * d + 1) + 1;

            }

            // 出力
            out.println(ans);

        }

    }
}



Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
  	cin >> n;
  	if(n<600) cout << "8\n";
  	else if(n<800) cout << "7\n";
  	else if(n<1000) cout << "6\n";
  	else if(n<1200) cout << "5\n";
  	else if(n<1400) cout << "4\n";
  	else if(n<1600) cout << "3\n";
  	else if(n<1800) cout << "2\n";
  	else cout << "1\n";
  
  	return 0;
 
}

Measured memory_bytes: 3416
// ---------- begin ModInt ----------
const MOD: u32 = 1_000_000_007;

#[derive(Clone, Copy)]
struct ModInt(u32);

impl std::ops::Add for ModInt {
    type Output = ModInt;
    fn add(self, rhs: ModInt) -> Self::Output {
        let mut d = self.0 + rhs.0;
        if d >= MOD {
            d -= MOD;
        }
        ModInt(d)
    }
}

impl std::ops::AddAssign for ModInt {
    fn add_assign(&mut self, rhs: ModInt) {
        *self = *self + rhs;
    }
}

impl std::ops::Sub for ModInt {
    type Output = ModInt;
    fn sub(self, rhs: ModInt) -> Self::Output {
        let mut d = self.0 + MOD - rhs.0;
        if d >= MOD {
            d -= MOD;
        }
        ModInt(d)
    }
}

impl std::ops::SubAssign for ModInt {
    fn sub_assign(&mut self, rhs: ModInt) {
        *self = *self - rhs;
    }
}

impl std::ops::Mul for ModInt {
    type Output = ModInt;
    fn mul(self, rhs: ModInt) -> Self::Output {
        ModInt((self.0 as u64 * rhs.0 as u64 % MOD as u64) as u32)
    }
}

impl std::ops::MulAssign for ModInt {
    fn mul_assign(&mut self, rhs: ModInt) {
        *self = *self * rhs;
    }
}

impl std::ops::Neg for ModInt {
    type Output = ModInt;
    fn neg(self) -> Self::Output {
        ModInt(if self.0 == 0 {0} else {MOD - self.0})
    }
}

impl std::fmt::Display for ModInt {
    fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result {
        write!(f, "{}", self.0)
    }
}

impl std::str::FromStr for ModInt {
    type Err = std::num::ParseIntError;
    fn from_str(s: &str) -> Result<Self, Self::Err> {
        let val = s.parse::<u32>()?;
        Ok(ModInt::new(val))
    }
}

impl From<usize> for ModInt {
    fn from(val: usize) -> ModInt {
        ModInt((val % MOD as usize) as u32)
    }
}

#[allow(dead_code)]
impl ModInt {
    pub fn new(n: u32) -> ModInt {
        ModInt(n % MOD)
    }
    pub fn zero() -> ModInt {
        ModInt(0)
    }
    pub fn one() -> ModInt {
        ModInt(1)
    }
    pub fn pow(self, mut n: u32) -> ModInt {
        let mut t = ModInt::one();
        let mut s = self;
        while n > 0 {
            if n & 1 == 1 {
                t *= s;
            }
            s *= s;
            n >>= 1;
        }
        t
    }
    pub fn inv(self) -> ModInt {
        assert!(self.0 > 0);
        self.pow(MOD - 2)
    }
}
// ---------- end ModInt ----------

use proconio::*;

fn run() {
    input! {
        k: usize,
    }
    let n = 3;
    let mut memo = vec![ModInt::zero(); k + 1];
    for i in (1..=k).rev() {
        let mut way = ModInt::from(k / i).pow(n);
        let mut j = 2 * i;
        while let Some(&v) = memo.get(j) {
            way -= v;
            j += i;
        }
        memo[i] = way;
    }
    let mut ans = ModInt::zero();
    for (i, c) in memo.into_iter().enumerate() {
        ans += ModInt::from(i) * c;
    }
    println!("{}", ans);
}

fn main() {
    run();
}


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

int main() {
  int N;
  int c=100000000;
  cin >> N;
	for(int i=0;i<N;i++){
	int ai;
      int bi=0;
      cin>>ai;
      for(int k=0;k<1000;k++){
      if(ai%2!=0){break;}
        else{ai/=2;
            bi++;}
      }
      if(c>=bi){c=bi;}
      
      }
  cout<<c<<endl;
}



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

int n, m;
bool mat[50][50];
bool visited[50];

void dfs(int u) {
  visited[u] = true;
  rep(i, n) {
    if (mat[u][i] && !visited[i]) dfs(i);
  }
}

bool solve() {
  rep(i, n) visited[i] = false;
  dfs(0);
  rep(i, n) if (!visited[i]) return false;
  return true;
}

int main() {
  cin >> n >> m;
  int a[m], b[m];
  rep(i, m) {
    cin >> a[i] >> b[i];
    --a[i]; --b[i];
    mat[a[i]][b[i]] = mat[b[i]][a[i]] = true;
  }

  int ans = 0;
  rep(i, m) {
    mat[a[i]][b[i]] = mat[b[i]][a[i]] = false;
    if (!solve()) ++ans;
    mat[a[i]][b[i]] = mat[b[i]][a[i]] = true;
  }
  cout << ans << endl;
  return 0;
}

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

using namespace std;

using ll = long long int;
using ull = unsigned long long int;
#define rep(i, a, b) for(int i = (a); i < (b); ++i )
#define rrep(i, a, b) for(int i = (a); i > (b); --i )
#define REP(i, a, b) for(int i = (a); i <= (b); ++i )
#define RREP(i, a, b) for(int i = (a); i >= (b); --i )
#define llrep(i, a, b) for(ll i = (a); i < (b); ++i )
#define llrrep(i, a, b) for(ll i = (a); i > (b); --i )
#define llREP(i, a, b) for(ll i = (a); i <= (b); ++i )
#define llRREP(i, a, b) for(ll i = (a); i >= (b); --i )
#define ullrep(i, a, b) for(ull i = (a); i < (b); ++i )
#define ullrrep(i, a, b) for(ull i = (a); i > (b); --i )
#define ullREP(i, a, b) for(ull i = (a); i <= (b); ++i )
#define ullRREP(i, a, b) for(ull i = (a); i >= (b); --i )



int D, N;

int main() {
    cin >> D >> N;
    ull ans = 1;
    rep(i, 0, D) {
        ans *= 100;
    }
    if (N == 100) {
        N = N+1;
    }
    cout << ans * N << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=1;i<=n;i++)
#define drep(i,n) for(int i=n;i>=0;i--)
#define MAX 131072
#define B 100
#define dpb push_back
#define fi first
#define se second
typedef pair<int, int> P;
typedef long long ll;
const int inf = 1e9;
const ll INF = 2147483647;
//__gcd(a,b), __builtin_popcount(a);

int n;
ll dat[MAX*2], add[MAX*2];
void init(int m){
	n = 1;
	while(n < m)n *= 2;
	for(int i = 0;i < 2*n;i++)dat[i] = INF;
	for(int i = 0;i < 2*n;i++)add[i] = -1;
}

void lazy_update(int k){
	if(add[k] == -1)return;
	if(k < n-1){
		add[k*2+1] = add[k];
		add[k*2+2] = add[k];
	}
	add[k] = -1;
}

ll update(int a, int b, int x, int k, int l, int r){
	if(add[k] != -1)dat[k] = add[k];
	if(r <= a || b <= l)return dat[k];
	if(a <= l && r <= b){
		add[k] = dat[k] = x;
		return dat[k];
	}
	lazy_update(k);
	ll vl = update(a, b, x, k*2+1, l, (l+r)/2);
	ll vr = update(a, b, x, k*2+2, (l+r)/2, r);
	dat[k] = min(vl, vr);
	return dat[k];
}

ll find(int a, int b, int k, int l, int r){
	if(add[k] != -1)dat[k] = add[k];
	if(r <= a || b <= l)return INF;
	if(a <= l && r <= b)return dat[k];
	lazy_update(k);
	ll vl = find(a, b, k*2+1, l, (l+r)/2);
	ll vr = find(a, b, k*2+2, (l+r)/2, r);
	return min(vr, vl);
}

int main(){
	int m, q, c, s, t, x;
	scanf("%d%d", &m, &q);
	init(m);
	while(q--){
		scanf("%d", &c);
		if(c == 0){
			scanf("%d%d%d", &s, &t, &x);
			update(s, t+1, x, 0, 0, n);
		}else{
			scanf("%d%d", &s, &t);
			ll ans = find(s, t+1, 0, 0, n);
			printf("%lld\n", ans);
		}
	}
	return 0;
}



Measured memory_bytes: 7284
import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')


N,D=map(int,input().split())
X=[list(map(int,input().split())) for _ in range(N)]
a=0
cnt=0

for i in range(N):
	for j in range(i+1,N):
		for k in range(D):
			a+=(X[i][k]-X[j][k])**2
		if int(a**.5)**2==a:
			cnt+=1
		a=0
		
			
print(cnt)	
		
		

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i < (n+1); ++i)
using namespace std;
using ll = long long;
const ll INF = +10010010000;

typedef pair<ll,ll> P;
const ll MO = 1000000007;


vector<int> to[200005];
vector<int> ans;


void dfs(int i, int p=-1){
    for(auto ele : to[i]){
        // 親と子と子の子の三要素を取ることができる.
        if(ele==p)continue;
        ans[ele]+=ans[i];
        dfs(ele,i);
    }
}

int main(){
    int n,q;
    cin >> n >> q;
    rep(i,n-1){
        int a,b;
        cin >> a >> b;
        --a;--b;
        to[a].push_back(b);
        to[b].push_back(a);
    }
    // 0埋めされる
    ans.resize(n);
    rep(i,q){
        int p,x;
        cin >> p>>x;
        --p;
        ans[p] += x;
    }
    dfs(0);
    rep(i,n){
        cout << ans[i] << endl;
    }
    return 0;
}

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

int main() {
    int h, w;
    cin >> h >> w;
    string s[h];
    for (int i = 0; i < h; i++) {
        cin >> s[i];
    }
    short table[2][h][w];
    for (int i = 0; i < h; i++) {
        fill(table[0][i], table[0][i] + w, 0);
        fill(table[1][i], table[1][i] + w, 0);
        if (s[i][0] == '.')
            table[0][i][0] = 1;
        for (int j = 1; j < w; j++) {
            if (s[i][j] == '.')
                table[0][i][j] = table[0][i][j - 1] + 1;
            else
                table[0][i][j] = 0;
        }
    }
    for (int i = 0; i < h; i++) {
        for (int j = w - 2; j >= 0; j--) {
            if (s[i][j] == '.')
                table[0][i][j] = max(table[0][i][j + 1], table[0][i][j]);
        }
    }
    for (int j = 0; j < w; j++) {
        if (s[0][j] == '.')
            table[1][0][j] = 1;
        for (int i = 1; i < h; i++) {
            if (s[i][j] == '.')
                table[1][i][j] = table[1][i - 1][j] + 1;
            else
                table[1][i][j] = 0;
        }
    }
    for (int j = 0; j < w; j++) {
        for (int i = h - 2; i >= 0; i--) {
            if (s[i][j] == '.')
                table[1][i][j] = max(table[1][i + 1][j], table[1][i][j]);
        }
    }
    int ans = 0;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            //cout << table[0][i][j] + table[1][i][j] - 1 << endl;
            ans = max(ans, table[0][i][j] + table[1][i][j] - 1);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 19968
#include <bits/stdc++.h>
#include <algorithm>
#include <string>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int A, P;
    cin >> A >> P;
    cout << ((A * 3 + P) / 2) << endl;
    return 0;
}

Measured memory_bytes: 256
n,m=map(int,input().split())
H=list(map(int,input().split()))
A=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1;b-=1
    A[a].append(b)
    A[b].append(a)
ans=0
for i in range(n):
    for j in A[i]:
        if H[j]>=H[i]:break
    else:
        ans+=1
print(ans)

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

constexpr int N_max = 5000;
constexpr int len_max = N_max / 2;

int main() {
    int n;
    string str;
    cin >> n >> str;
    const char *const s = str.c_str();

    int lo = 0;
    int hi = len_max + 1;
    while (lo + 1 < hi) {
        int len = (lo + hi) / 2;

        for (int pos = 0; pos + len + len <= n; pos++) {
            for (int pos2 = pos + len; pos2 + len <= n; pos2++) {
                if (strncmp(s + pos, s + pos2, len) == 0) {
                    goto found;
                }
            }
        }
        hi = len;
        continue;

    found:
        lo = len;
    }

    cout << lo;
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define __ <<' '<<
#define ___ <<' '
#define bash push_back
#define ALL(x) x.begin(),x.end()
//#define int long long

struct IoSetup {IoSetup() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout <<fixed<<setprecision(12);
    cerr <<fixed<<setprecision(12);
}}IoSetup;

using ll = long long;
using pii = pair<int, int>;
constexpr int INF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int SMOD = 1000000007;
constexpr int NMOD = 998244353;
constexpr int dx[]={1,0,-1,0,1,1,-1,-1};
constexpr int dy[]={0,1,0,-1,-1,1,-1,1};

inline bool inside(int x,int y,int w,int h){return (x>=0 && y>=0 && x<w && y<h);}
template<class T>bool chmax(T &a, const T &b){return(a<b?a=b,true:false);}
template<class T>bool chmin(T &a, const T &b){return(a>b?a=b,true:false);}
inline int qp(int a,ll b,int mo){ll ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}

int n, a, b, c;
vector<string> s;
stack<char> sc;
bool dfs(int i, int ac, int bc, int cc) {
    if(ac < 0 or bc < 0 or cc < 0) return false;
    if(i == n) return true;
    
    if(s[i] == "AB") {
        if(dfs(i+1, ac+1, bc-1, cc)) {
            sc.push('A');
            return true;
        }
        if(dfs(i+1, ac-1, bc+1, cc)) {
            sc.push('B');
            return true;
        }
    }
    else if(s[i] == "AC") {
        if(dfs(i+1, ac+1, bc, cc-1)) {
            sc.push('A');
            return true;
        }
        if(dfs(i+1, ac-1, bc, cc+1)) {
            sc.push('C');
            return true;
        }
    }
    else {
        if(dfs(i+1, ac, bc+1, cc-1)) {
            sc.push('B');
            return true;
        }
        if(dfs(i+1, ac, bc-1, cc+1)) {
            sc.push('C');
            return true;
        }
    }
    return false;
}


signed main() {

    cin >> n >> a >> b >>  c;
    s.resize(n);
    
    for(int i = 0; i < n; i++) {
        cin >> s[i];
    }

    if(dfs(0, a, b, c)) {
        cout << "Yes\n";
        while(!sc.empty()) {
            cout << sc.top() << endl;
            sc.pop();
        }
    }
    else
        cout << "No\n";
  
    return 0;
}



Measured memory_bytes: 12712
N=int(input())
RW=input()

RightW=0
tesu=0

LeftW=0
LeftR=0

numW=0
numR=0

for i in RW:
  if i=="R":
    numR+=1
  else:
    numW+=1

for i in range(numR):
  if RW[i]=="W":
    LeftW+=1
  else:
    LeftR+=1

print(LeftW)



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

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

  if (abs(A - C) <= D || (abs(A - B) <= D && abs(B - C) <= D)) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>

int main(){
	int a,b;
	char op;
	while(1){
		scanf("%d %c %d",&a,&op,&b);
		if(op=='?'){break;}
		if(op=='+'){printf("%d\n",a+b);}
		if(op=='-'){printf("%d\n",a-b);}
		if(op=='*'){printf("%d\n",a*b);}
		if(op=='/'){printf("%d\n",a/b);}
	}
	return 0;
}

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

int main(){
	ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
	
	int n,k,ans = 0;
	cin>>n>>k;
	for(int i=0;i<n;i++){
		int x;
		cin>>x;
		ans += min(2*x,2*(k-x));
	}
	cout<<ans;
	
	return 0;
}


Measured memory_bytes: 256
#include<algorithm>//everybody dies in their nightmares
#include<iostream>
#include<cstring>
#include<cstdio>
#include<set>
#include<map>
#include<queue>
#include<deque>
#include<string>
#include<vector>
#include<sstream>
#include<cmath>
//#include<unordered_set>
//#include<unordered_map>
#include<bitset>
#define f(i,a,b) for(register int i=a;i<=b;++i)
#define ff(i,a,b) for(register int i=a;i>=b;--i)
#define debug(x) cerr << #x << " : " << x << " " << endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<string, string> pss;
const ll mod = 1e9 + 7;
const double tiaohe = 0.57721566490153286060651209;
ll oula(ll x) { ll res = x;f(i, 2, x / i) { if (x % i == 0) { res = res / i * (i - 1);while (x % i == 0) x /= i; } }if (x > 1) res = res / x * (x - 1);return res; }
ll quickmod(ll a, ll n, ll m) { ll s = 1;while (n) { if (n & 1) { s = s * a % m; }a = (a*a) % m;n = n / 2; }return s; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
void ex_gcd(ll a, ll b, ll &x, ll &y, ll &d) { if (!b) { d = a, x = 1, y = 0; } else { ex_gcd(b, a % b, y, x, d);y -= x * (a / b); } }
ll inv(ll t, ll p) { ll d, x, y;ex_gcd(t, p, x, y, d);return d == 1 ? (x % p + p) % p : -1; }
bool isPrime(ll x) { if (x == 2)return true;if (x % 2 == 0)return false;for (ll i = 2;i*i <= x;i++) if (x % i == 0)return false; return true; }
//double a = log(n) +tiaohe + 1.0 / (2 * n);
double eqa = (1 + sqrt(5.0)) / 2.0;

const int N = 6e5 + 5;
int t;
int a[N];
int main()
{
	int n;
	while (cin >> n)
	{
		map<int, int> mp;ll ans = 0;
		f(i, 1, n)
		{
			scanf("%d", &a[i]);
			ans += mp[i - a[i]];
			mp[a[i] + i]++;
		}
	
		cout << ans << endl;
	}
	return 0;
}



Measured memory_bytes: 21532
#include "bits/stdc++.h"
using namespace std;
const int maxn = 300300;
int c[maxn], s[maxn], f[maxn];
int main(){
    int n;
    cin >> n;
    for(int e = 0; e < n-1; e++) cin >> c[e] >> s[e] >> f[e];
    for(int e = 0; e < n; e++){
        int cur_time = s[e] + c[e];
        for(int g = e + 1; g < n-1; g++){
            if(s[g] >= cur_time) cur_time = s[g];
            else{
                int diff = (cur_time - s[g]);
                cur_time = s[g] + ((diff + f[g] - 1)/f[g])*f[g];
            }
            cur_time += c[g];
        }
        printf("%d\n", cur_time);
    }
    return 0;
}


Measured memory_bytes: 256
// https://atcoder.jp/contests/abc047/tasks/abc047_a
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) FOR(i, 0, n)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()

bool dp[100][100];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int W, H, N;
    cin >> W >> H >> N;
    REP(i, N) {
        int x, y, z;
        cin >> x >> y >> z;
        if (z == 1) {
            REP(j, x) REP(k, H) dp[k][j] = true;
        } else if (z == 2) {
            FOR(j, x, W) REP(k, H) dp[k][j] = true;
        } else if (z == 3) {
            REP(j, y) REP(k, W) dp[j][k] = true;
        } else {
            FOR(j, y, H) REP(k, W) dp[j][k] = true;
        }
    }

    int ans = 0;
    REP(i, H) REP(j, W) {
        if (!dp[i][j])
            ans++;
    }
    cout << ans << endl;

    return 0;
}


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

signed main() {
    int N;
    cin >> N;
    int a[N];
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
    int ans = 0;
    for (int i = 0; i < N; i ++) {
        while (a[i] > 0 && a[i] %2 == 0) a[i] /= 2, ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
while 1:
 a=b=0;n=int(input())
 if n==0:break
 while n:
  s,t=map(int,input().split())
  if s>t:a+=s+t
  elif s<t:b+=s+t
  else:a+=s;b+=t
  n-=1
 print(a,b)


Measured memory_bytes: 5616
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
#include <cassert>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
#include <iomanip>
#include <fstream>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define chmax(a,b) (a<b?(a=b,1):0)
#define chmin(a,b) (a>b?(a=b,1):0)
#define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w)
const int INF = 1<<29;
const double EPS = 1e-8;
const double PI = acos(-1);
typedef long long ll;
typedef pair<int,int> pii;

int e[100];
int c[100];
int h[100];
int a[100];
int dp[101][101];
int dp_tr[101][101];            // [i][j] = i種類のトレーニングを行って，体力j消費するときの消費カロリーの最大
int dp_d[10000];             // [i] = カロリーがi以下なドーナツの食べ方の最大幸福度

int main() {
  int S,T,U,N,O,D;
  while(cin>>S>>T>>U>>N>>O>>D) {
    REP(i,T) {
      cin >> e[i] >> c[i];
    }
    REP(i,N) {
      cin >> h[i] >> a[i];
    }
    memset(dp_tr,-1,sizeof(dp_tr));
    dp_tr[0][0] = 0;
    REP(i,T) {
      for (int j=T-1; j>=0; --j) {
        REP(k,101) {
          if (dp_tr[j][k] == -1) continue;
          if (k+e[i] <= 100) {
            chmax(dp_tr[j+1][k+e[i]], dp_tr[j][k]+c[i]);
          }
        }
      }
    }
    memset(dp_d,0,sizeof(dp_d));
    REP(i,N) {
      REP(k,10001) {
        if (k+a[i] <= 10000) {
          chmax(dp_d[k+a[i]], dp_d[k] + h[i]);
        }
      }
    }
    // REP(i,21) {
    //   cout << i << " " << dp_tr[U][i] << " " << dp_d[i] << endl;
    // }
    memset(dp,-1,sizeof(dp));
    dp[0][S] = 0;
    REP(i,D) {
      REP(j,S+1) {
        if (dp[i][j] == -1) continue;
        REP(k,j+1) {
          if (dp_tr[U][k] == -1) continue;
          chmax(dp[i+1][min(S,j-k+O)], dp[i][j] + dp_d[dp_tr[U][k]]);
        }
      }
    }
    cout << *max_element(dp[D],dp[D]+S+1) << endl;
  }
}

Measured memory_bytes: 1288
eval [103,101,116,115,10,97,32,61,32,98,32,61,32,49,10,36,60,46,109,97,112,32,100,111,32,124,115,124,10,32,32,110,97,44,110,98,32,61,32,115,46,115,112,108,105,116,46,109,97,112,32,38,58,116,111,95,114,10,32,32,116,32,61,32,91,97,47,110,97,44,32,98,47,110,98,93,46,109,97,120,46,99,101,105,108,10,32,32,97,44,98,32,61,32,110,97,42,116,44,110,98,42,116,10,101,110,100,10,112,32,40,97,43,98,41,46,116,111,95,105,10].map(&:chr).join

Measured memory_bytes: 2044
n=int(input())
import collections
import itertools
l=['M','A','R','C','H']
x=[]
for i in range(n):
  s=input()
  if s[0] in l:
    x.append(s[0])
c=collections.Counter(x)
ans=0
for p in itertools.combinations('MARCH',3):
  cnt=1
  for j in range(3):
    cnt*=c[p[j]]
  ans+=cnt
print(ans)

Measured memory_bytes: 10100
#include<bits/stdc++.h>
using namespace std;
using UL = unsigned long;
using ULL = unsigned long long;
using LL = long long;
#define rep(i, n) for(UL i = 0; i < (n); i++)

struct Problem {

    void Solve() {
        UL N; cin >> N;
        vector<double> A(N); rep(i, N) cin >> A[i];
        vector<double> B(N); rep(i, N) cin >> B[i];
        for (UL d = 1; d <= 3; d++) {
            double ans = 0;
            rep(i, N) ans += pow(abs(A[i] - B[i]), (double)d);
            ans = pow(ans, 1.0 / (double)d);
            cout << ans << endl;
        }
        {
            double ans = 0;
            rep(i, N) ans = max(ans, abs(A[i] - B[i]));
            cout << ans << endl;
        }
    }
};
int main() {
    unique_ptr<Problem> p(new Problem());
    cout << fixed << setprecision(10);
    p->Solve();
    return 0;
}



Measured memory_bytes: 3420
#include <bits/stdc++.h>
#include<chrono>
using namespace std;
using ll = long long;

int main() {
  int N;
  cin >> N;
  vector<vector<int>> A(2, vector<int>(N));
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < N; j++) {
      cin >> A[i][j];
    }
  }
  priority_queue<int> ans;
  for (int k = 0; k < N; k++) {
    int sum = 0;
    for (int i = 0; i <= k; i++) {
      sum += A[0][i];
    }
    for (int i = k; i < N; i++) {
      sum += A[1][i];
    }
    ans.push(sum);
  }
  cout << ans.top() << endl;
}

  
  

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int data=0;int w=1; char ch=0;
    ch=getchar();
    while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();
    if(ch=='-') w=-1,ch=getchar();
    while(ch>='0' && ch<='9') data=(data<<3)+(data<<1)+ch-'0',ch=getchar();
    return data*w;
}
const int N=1e5+10;
const int inf=1e9;
int n,m;
struct node{
	int v,w,nxt;
}e[N<<2];
int fir[N],cnt=0;
int dis[N],isin[N];
inline void add(int u,int v,int w){
	e[++cnt]=(node){v,w,fir[u]};fir[u]=cnt;
}
priority_queue<pair<int,int> >q;
set<int>c[N];
inline void dj(){
	for(int i=1;i<=n;i++) dis[i]=inf;
	memset(isin,0,sizeof(isin));
    dis[1]=0;
    q.push(make_pair(0,1));
    while(!q.empty()){
    	int u=q.top().second;q.pop();
    	if(isin[u]) continue;
    	isin[u]=1;
    	for(int i=fir[u];i;i=e[i].nxt){
    		int v=e[i].v,w=c[u].count(e[i].w)?0:1;
    		if(dis[v]>dis[u]+w){
    			dis[v]=dis[u]+w;
    			q.push(make_pair(-dis[v],v));
    			c[v].clear();
    			c[v].insert(e[i].w);
			}
			else if(dis[v]==dis[u]+w){
				c[v].insert(e[i].w);
			}
		}
	}
}
int main(){
	n=read();m=read();
	if(m==0) {
		puts("-1");return 0;
	}
	for(int i=1;i<=m;i++){
		int x=read(),y=read(),v=read();
		add(x,y,v);add(y,x,v);
	}
	dj();
	printf("%d\n",dis[n]==inf?-1:dis[n]);
	
	return 0;
}


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

int64_t solve();

int main()
{
	printf("%lld\n", solve());

	return 0;
}

int64_t solve()
{
	int N, M;
	scanf("%d%d", &N, &M);
	std::vector<std::array<int, 3>> edges(M);
	for (auto& e: edges)
	{
		for (auto& f: e)
			scanf("%d", &f);
		e[0]--;
	}
	std::sort(edges.begin(), edges.end());
	edges.push_back({1 << 30, 1 << 30, 1 << 30});
	using pii = std::pair<int64_t, int>;
	std::priority_queue<pii, std::vector<pii>, std::greater<pii>> pq;	// {dist, r}, [l, r)
	pq.push({0, 1});
	for (int i{}, e_i{}; i < N; i++)
	{
		while (!pq.empty() && pq.top().second <= i) pq.pop();
		if (pq.empty()) return -1;
		auto now{pq.top()};
		while (edges[e_i][0] == i)
		{
			pq.push({now.first + edges[e_i][2], edges[e_i][1]});
			e_i++;
		}
	}

	if (pq.empty()) return -1;
	else return pq.top().first;
}

Measured memory_bytes: 6048
#include<stdio.h>
int main(){
  int n,k,i,j;
  int A[200001];
  scanf("%d%d",&n,&k);
  for(i=0;i<n;i++)scanf("%d",&A[i]);
  for(i=0;i<(k<42?k:42);i++){
    int B[200000]={0},s=0;
    for(j=0;j<n;j++){B[(j-A[j]>0?j-A[j]:0)]++;B[n<j+A[j]+1?n:j+A[j]+1]--;}
    for(j=0;j<n;j++){s+=B[j];A[j]=s;}
  }
  for(i=0;i<n;i++)printf("%d ",A[i]);
}


Measured memory_bytes: 3288