akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vin=vector<int>;
using vll=vector<long long>;
using vvin=vector<vector<int>>;
using vvll=vector<vector<long long>>;
using vstr=vector<string>;
using vvstr=vector<vector<string>>;
using vch=vector<char>;
using vvch=vector<vector<char>>;
using vbo=vector<bool>;
using vvbo=vector<vector<bool>>;
using vpii=vector<pair<int,int>>;
using pqsin=priority_queue<int,vector<int>,greater<int>>;
#define mp make_pair
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,s,n) for(int i=(s);i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define decp(n) cout<<fixed<<setprecision((int)n)
const ll inf=1e9+7;
const ll INF=1e18;

int main(){
    int n,m;cin>>n>>m;
    vin s(n),t(m);
    rep(i,n)cin>>s[i];
    rep(i,m)cin>>t[i];
    vvll dp(n+1,vll(m+1));
    rep(i,n)rep(j,m){
        dp[i+1][j+1]=dp[i+1][j]+dp[i][j+1]-dp[i][j];
        if(s[i]==t[j])dp[i+1][j+1]+=dp[i][j]+(ll)1;
        dp[i+1][j+1]%=inf;
        if(dp[i+1][j+1]<0)dp[i+1][j+1]+=inf;
    }
    cout<<(dp[n][m]+(ll)1)%inf<<endl;//空文字列分追加
}

Measured memory_bytes: 34564
N, K = map(int,input().split())
dices = list(map(int,input().split()))
list =[]
check=0
for i in range(K):
    check+=dices[i]
list.append(check)
for j in range(N-K):
    check -= dices[j]
    check += dices[j+K]
    list.append(check)    
print((max(list)+K)/2)

Measured memory_bytes: 32012
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int INF=(int)1e9;

int solve(const int low,const vector<int>& ls)
{
	const int n=ls.size();
	vector<int> dp(n+1);
	dp[0]=low;
	
	for(int position=0;position<n;position++)
	{
		int piece_length=0;
		int& value=dp[position+1];
		
		value=INF;
		
		for(int piece_left=position;piece_left>=0;piece_left--){
			
			piece_length+=ls[piece_left];
			
			if(position==n-1&&piece_left==0){
				continue;
			}
			
			if(piece_length>=low){
				const int high=max(piece_length,dp[piece_left]);
				value=min(value,high);
			}
		}
	}
	return dp[n]-low;
}

int main()
{
	int n;
	vector<int> ls;
	
	cin>>n;
	ls.resize(n);
	for(int i=0;i<n;i++){
		cin>>ls[i];
	}
	
	int answer=INF;
	for(int left=0;left<n;left++){
			int total_length=0;
			for(int right=left;right<n;right++){
				total_length+=ls[right];
				int temp=solve(total_length,ls);
				answer=min(answer,temp);
			}
	}
	cout<<answer<<endl;
}


Measured memory_bytes: 3120
#include<bits/stdc++.h>
using namespace std;
int a[105],b[105];
int n,m;
int x,y;
int main() {
	std::ios::sync_with_stdio(false);
	cin>>n>>m>>x>>y;
	for(int i=0;i<n;i++) cin>>a[i];
	for(int i=0;i<m;i++) cin>>b[i];
	sort(a,a+n);
	sort(b,b+m);
	for(int i=-105;i<105;i++) 
		if(i>a[n-1]&&i>x&&i<=b[0]&&i<=y) {
			cout<<"No War";
			return 0;
		}
	cout<<"War";
	return 0;
}


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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define ff first
#define ss second
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int S = int(1e5)+10;
const ll MOD = ll(1e9)+7;

int dp[S], n, h[S], k;


int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cin >> n >> k;
	rep(i, 0, n) 
		cin >> h[i];
	rep(i, 1, n) {
		dp[i] = dp[i-1] + abs(h[i] - h[i-1]);
		for(int j = 2; j <= k && i - j >= 0; j++)
			dp[i] = min(dp[i], dp[i-j] + abs(h[i] - h[i-j]));
	}
	cout << dp[n-1] << endl;
	return 0;
}

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

using namespace std;
#define endl "\n"
#define ll long long
#define ld long double
#define pll pair<long long,long long>
#define vll vector<long long>
#define all(x) x.begin(),x.end()
#define pb push_back
#define Fo(i,k,n) for(ll i=k;i<=n;i+=1)
#define deb(x) cout << #x << "=" << x << endl
#define in(a,n) Fo( i,0,n-1)cin>>a[i]
#define out(a,n) Fo( i,0,n-1)cout<<a[i]<<" ";cout<<endl
#define IOS     ios_base::sync_with_stdio(0); cin.tie(NULL);
const ll N=2*1e6+1;


int main() {
	IOS
    ll t=1;
	//cin>>t;	
	
	Fo(_,1,t)
	{
	   //cout<<"Case #"<<_<<": ";
	   ld d,s,tt;
	   cin>>d>>tt>>s;
	   if(d/s<=tt)cout<<"Yes";
	   else cout<<"No";
	   
	   


	   cout<<endl;
	   
	}
	
    
}

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

int main() {

    string s;
    cin >> s;

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

    string dream = "maerd", dreamer = "remaerd", erase = "esare", eraser = "resare";

    int index = 0;

    while(index != s.size()) {
        string sub = s.substr(index, 5);

        if(sub == dream || sub == erase) {
            index += 5;
            continue;
        }

        sub = s.substr(index, 6);
        
        if(sub == eraser) {
            index += 6;
            continue;
        }

        sub = s.substr(index, 7);

        if(sub == dreamer) {
            index += 7;
            continue;
        }

        cout << "NO" << endl;
        return 0;

    }

    cout << "YES" << endl;

    return 0;


}

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

using namespace std;

int main()
{
   int a,b;
   while(scanf("%d %d",&a,&b)==2)
   {
       long long t;int s;
   if(a==0)
       s=1;
   if(a==1)
      s=100;
   if(a==2)
    s=10000;
   if(a==3)
    s=1000000;

   t=s*b;
   if(b!=100)
     printf("%lld\n",t);
    else
        printf("%d\n",s+t);
   }

    return 0;
}


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

using ll = long long;
using pll = pair<ll,ll>;
const ll INF = 1ll<<60;

void chmax (pll &a, pll b) {
    if (a.first < b.first) {
        a.second = max(a.first, b.second);
        a.first = b.first;
    }
    else a.second = max(a.second, b.first);
}

int main() {
    int n; cin >> n;
    vector<ll> a(1<<n);
    vector<pll> dp(1<<n);
    rep(i,1<<n) {
        cin >> a[i];
        dp[i] = pll(a[i], -INF);
    }

    // 高速ゼータ変換
    rep(j,n) rep(i,1<<n) if (i & 1<<j) chmax(dp[i], dp[i^(1<<j)]);

    ll ans = -INF;
    rep(i,1<<n) {
        ans = max(ans, dp[i].first + dp[i].second);
        if (i) cout << ans << endl;
    }
    return 0;
}

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

using namespace std;

#define REP(i,m) for(long long i=0; i<m; i++)
#define FOR(i,n,m) for(long long i=n; i<m; i++)
#define INF 1000000000
#define INFL 10000000000000000LL
#define ALL(v) v.begin(),v.end()
#define pb push_back
#define ll long long int
#define P pair<ll, ll>

ll gcd(ll a, ll b){
  if(b == 0) return a;
  else return gcd(b, a%b);
}

int main() {
  ll n, x;
  cin >> n >> x;
  cout << 3*(n-gcd(n, x)) << endl;
  return 0;
}

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

using namespace std;

char c[1010][1010];
int dp[1010][1010];
int mod = 1e9 + 7;
int n,m;
int main() {
    cin >> n >> m;

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> c[i][j];

    dp[0][0] = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if(c[i][j] == '#') continue;
            if(i) dp[i][j] += dp[i - 1][j];
            dp[i][j] %= mod;
            if(j) dp[i][j] += dp[i][j - 1];
            dp[i][j] %= mod;
        }
    }

    cout << dp[n - 1][m - 1] << "\n";
    return 0;
}


Measured memory_bytes: 5248
def valid(i,j):
  return i>=0 and i<h and j>=0 and j<w

def get_adj(i,j):
  points = []
  for k in range(8):
    if valid(x[k]+i,y[k]+j):
      points.append((x[k]+i,y[k]+j))
  return points
h,w = map(int,input().split())
mat = []
for _ in range(h):
  mat.append(list(input()))
x = [0,0,1,1,-1,-1,1,-1]
y = [1,-1,1,-1,1,-1,0,0]
for i in range(h):
  for j in range(w):
    if mat[i][j]=='#':
      continue
    bombs = 0
    for p in get_adj(i,j):
      if mat[p[0]][p[1]]=='#':
        bombs+=1
    mat[i][j] = bombs
for i in range(h):
  for j in range(w):
    print(mat[i][j],end='')
  print()

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

int main()
{
	int N, K, Q;
	int p[100010];

	cin >> N >> K >> Q;

	for (int i = 0; i < N; i++)
		p[i] = 0;

	for (int i = 0; i < Q; i++)
	{
		int a;
		cin >> a;
		p[a - 1]++;
	}

	for (int i = 0; i < N; i++)
		if (K - (Q - p[i]) > 0)
			cout << "Yes\n";
		else
			cout << "No\n";

	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#include<ctype.h>
# define pb push_back
#define fst first
#define sec second
#define For(i,a,b) for(int i=a;i<b;i++)
#define ll long long int
#define ull unsigned long long int
#define mod 1000000007
#define fo(i,n) for(ll i=0;i<n;i++)
#define endl "\n"
#define rev(i,n) for(ll i=n-1;i>=0;i--)
#define fo1(i,n) for(ll i=1;i<=n;i++)
#define boolsize 1000001
#define pi pair<ll,ll>
#define vi vector<ll>
#define vii vector<pi>
using namespace std;
template<typename T>
void showvector(vector <T> v)
{
    for(T x:v)
        cout<<x<<" ";
    cout<<endl;

}
template<typename T>
void showvector1(vector <T> v)
{
    ll n=v.size();
    fo1(i,n-1)
        cout<<v[i]<<endl;

}
template<typename T>
void showset(set <T> s)
{
    for(T x: s)
        cout<<x<<" ";
    cout<<endl;
}
template<class T>
void showvectorpair(vector<T> v)
{
    for(auto it=v.begin();it!=v.end();it++)
        cout<<it->first<<" "<<it->second<<endl;
    cout<<endl;
}
template<typename T,typename P>
void showmap(map <T,P> m)
{
    for(auto it=m.begin();it!=m.end();it++)
        cout<<it->first<<" "<<it->second<<endl;
    cout<<endl;
}
template<typename T>
bool comp(T a,T b)
{
    return (a>b);
}
template<class T>
bool comppair(T a,T b)
{
    if(a.first==b.first)
        return(a.second>b.second);
    return (a.first>b.first);
}
bool sameparity(ll a,ll b)
{
    return (a%2==b%2);
}
bool difparity(ll a,ll b)
{
    return !(a%2==b%2);
}
bool isprime(ll x)
{   if(x<=1)
     return false;
    for(ll i=2;i<=sqrt(x);i++)
    {
        if(x%i==0)
            return false;
    }
    return true;
}
bool iseven(ll x)
{
    return !(x%2);
}
bool isodd(ll x)
{
    return (x%2);
}
/// check for test case before submitting
void vfun()
{
    ll n,k;
    cin>>n;
    vector <ll> v(n);
    fo(i,n)
    cin>>v[i];

}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("inputh.txt", "r", stdin);
    freopen("outputh.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0); ///cant use scanf, printf
    cin.tie(0);cout.tie(0); /// no longer auto flush cout before each cin, remove for interactive
    //cout << fixed << setprecision(11); /// no scientific output
    ll test=1;
   // cin>>test;
    while(test--)
    {

            ll n;cin>>n;
            vi v(n);
            fo(i,n)
                cin>>v[i];
            sort(v.begin(),v.end());
            ll ans=0;
            fo(i,n-1)
            {
                for(ll j=i+1;j<n;j++)
                {
                    ll sum=v[i]+v[j];
                    auto it=lower_bound(v.begin(),v.end(),sum);
                    ans+=it-(v.begin()+j+1);
                }
            }
            cout<<ans;
//         if(vfun())
//            cout<<"YES\n";
//         else
//            cout<<"NO\n";
    }
}
///before sub
/// check for value of zero and single input in array
///loop vars,1LL in mult, equal, one, bounds, int v ll, endl, finish taking inputs
/// check whether test cases are given or not





Measured memory_bytes: 3644
from collections import deque
import math

N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]
XH.sort(key=lambda x: x[0])

# 爆発範囲がとても広く、全ての爆発が右端まで及ぶとひとまず考える
# 各xを見る際に、影響の及ばない爆発分のダメージは引く

# 合計の爆発回数
ans = 0
# 爆発ダメージの合計
total_damage = 0
# 各爆発の情報
dq = deque()

# 左端から順にモンスターを見る
for x, h in XH:
    # 爆発が及ばない場合
    while dq and dq[0][1] < x:
        dmg, rng = dq.popleft()
        total_damage -= dmg

    # 爆発させる必要がある場合
    if total_damage < h:
        # 残っているHPに更新
        h -= total_damage
        # 必要な爆発回数
        # cnt = math.ceil(h // A)
        cnt = (h + A - 1) // A
        ans += cnt
        # 爆発回数 * 単発のダメージ
        dmg = cnt * A
        total_damage += dmg
        # [爆発で与えるダメージ、及ぶ範囲の右端]
        dq.append((dmg, x + D * 2))

print(ans)


Measured memory_bytes: 60432
n,q=map(int,input().split())
s=input()
t=[0]*(n+1)
for i in range(n):
  t[i+1] = t[i] + (1 if s[i:i+2]=='AC' else 0)
for _ in range(q):
  l,r=map(int,input().split())
  print(t[r-1]-t[l-1])

Measured memory_bytes: 13076
import numpy as np

n, k = map(int, input().split())
s = [int(x) for x in input()]

memo = np.zeros(10 ** 5 + 1, dtype=np.int64)
W = min(2 * k, 10 ** 5)

current = 1
p = 0

for x in s:
    if x == current:
        memo[p] += 1
    else:
        current = 1 - current
        p += 1
        memo[p] += 1

ans = memo[:W + 1].sum()
x = ans

for r in range(2, 10 ** 5 + 1, 2):
    if r + W > 10 ** 5:
        break
    x = x - memo[r - 2] - memo[r - 1] + memo[r + W] + memo[r + W - 1]
    if x > ans:
        ans = x
print(ans)


Measured memory_bytes: 28540
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
#include <cstring>
#include <string>
#include <cmath>
#include <functional>
#include <queue>
#include <map>
using namespace std;

typedef long long ll;
const int M = 1e9 + 7;
const int N = 2e5 + 10;
const int MAX = 1e9 + 1;
//int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

map<int, int> mp1, mp2;

int main() {
    int i, j;
    int n;
    scanf("%d", &n);
    for (i = 0; i < n; ++i) {
        int t;
        scanf("%d", &t);
        ++mp1[t];
    }
    scanf("%d", &n);
    for (i = 0; i < n; ++i) {
        int t;
        scanf("%d", &t);
        ++mp2[t];
    }
    bool flag = true;
    for (map<int, int>::iterator it = mp2.begin(); it != mp2.end(); ++it) {
        if (it->second > mp1[it->first]) {
            flag = false;
            break;
        }

    }
    cout << (flag ? "YES" : "NO") << endl;
    return 0;
}


Measured memory_bytes: 18944
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		try(Scanner sc = new Scanner(System.in)){
			while(sc.hasNext()) {
				int h=sc.nextInt();
				int w=sc.nextInt();
				if((h|w)==0) break;
				int d=h*h+w*w;
				int d2=22500;
				int mini=0, minj=0;
				int count=0;
				for(int i=1; i<=150; i++) {
					for(int j=i+1; j<=150; j++) {
						if(i*i+j*j>d) {
							if(i*i+j*j<d2) {
								d2=i*i+j*j;
								mini=i; 
								minj=j;
							}
						}
						if(i>h && i*i+j*j==d && count==0) {
							d2=i*i+j*j;
							mini=i; 
							minj=j;
							count++;
						}
					}
				}
				System.out.printf("%d %d\n", mini, minj);
				
			}


		}
	}
}


Measured memory_bytes: 28092
#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++)
#define all(v) (v).begin(), (v).end()
#define pb(a) push_back(a)
using namespace std;
typedef long long LL;

int main()
{
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  int ans = 1010101010;
  rep(i, n)
  {
    int tmp = 0;
    while (a[i] % 2 == 0)
    {
      a[i] /= 2;
      tmp++;
    }
    ans = min(ans, tmp);
  }
  cout << ans << endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REP2(i, a, b) for (int i = (a); i < (int)(b); i++)
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<VS> VVS;
typedef vector<bool> VB;
typedef long long ll;
#define ALL(V) V.begin(), V.end()
template<class T,class U>bool chmin(T&a,const U&b){if(a<=b)return false;a=b;return true;}
template<class T,class U>bool chmax(T&a,const U&b){if(a>=b)return false;a=b;return true;}


string Main(string S, int Q, VVS& queries)
{
  string left = S;
  string right = "";
  bool flipped = false;
  for (VS q : queries) {
    if(q[0] == "1") {
      if(!flipped) flipped = true;
      else flipped = false;
    }
    else {
      if(q[1] == "1") {
        if(flipped) left += q[2];
        else right += q[2];
      }
      else {
        if(!flipped) left += q[2];
        else right += q[2];
      }
    }             
  }
  reverse(ALL(right));
  string ans = right + left;
  if(flipped) {
    reverse(ALL(ans));
  }
  return ans;

}

int main(void){
  	std::cin.tie(nullptr);
	  std::ios_base::sync_with_stdio(false);
	  std::cout << std::fixed << std::setprecision(15);
    string S;
    cin >> S;
    int Q;
    cin >> Q;
    VVS queries(Q);
    REP(i, Q) {
      VS query(3);
      cin >> query[0];
      if(query[0] == "2") {
        cin >> query[1] >> query[2];
      }
      queries[i] = query;
    }
    cout << Main(S, Q, queries) << endl;
    return 0;
}

Measured memory_bytes: 40200
#include <cstdio>
#include <algorithm>
#define lc(x) ((x)*2)
#define rc(x) ((x)*2+1)
using std::min;

const int INF = 10000000;
const int MAXN = 300000+10;

int N, Q;
char S[MAXN];
//Tree
int SIZE=1, Root=1;
int tag[8*MAXN];
int Min[8*MAXN]; //????¶´???
bool HaveR[8*MAXN]; //????????¬???

int change(int no, int l, int r, int pos){
    if(l==r){
        HaveR[no] = 1-HaveR[no];
        if(HaveR[no]) return 1;
        else return 2;
    }
    int mid = (l+r)/2;
    int tmp;
    if(pos <= mid) tmp = change(lc(no), l, mid, pos);
    if(mid < pos)  tmp = change(rc(no), mid+1, r, pos);
    HaveR[no] = HaveR[lc(no)] + HaveR[rc(no)];
    return tmp;
}

void maintain(int no){
    if(tag[no] != 0){
        Min[lc(no)] += tag[no];
        Min[rc(no)] += tag[no];
        tag[lc(no)] += tag[no];
        tag[rc(no)] += tag[no];
        tag[no] = 0;
    }
    if(no<SIZE) Min[no] = min(Min[lc(no)], Min[rc(no)]);
    return;
}

void puttag(int no, int l, int r, int ql, int qr, int k){
    if(r < ql || qr < l) return;
    if(ql<=l && r<=qr){
        Min[no] += k;
        tag[no] += k;
        return;
    }
    maintain(no);
    int mid = (l+r)/2;
    puttag(lc(no), l, mid, ql, qr, k);
    puttag(rc(no), mid+1, r, ql, qr, k);
    maintain(no);
    return;
}

int find_r(int no, int l, int r){
    if(l==r) return l;
    int mid = (l+r)/2;
    if(HaveR[lc(no)])
        return find_r(lc(no), l, mid);
    return find_r(rc(no), mid+1, r);
}
int find_min(int no, int l, int r){
    if(l==r) return l;
    maintain(no);
    int mid = (l+r)/2;
    if(Min[rc(no)] < 0)
        return find_min(rc(no), mid+1, r);
    return find_min(lc(no), l, mid);
}

void build_tree(){
    SIZE=1;
    while(SIZE < N) SIZE*=2; //1-Root
    int sum=0;
    for(int i=N ; i<=SIZE; i++){
        Min[SIZE+i] = INF;
    }
    for(int i=N-1 ; i>=0 ; i--){ //size,size+1..?????????
        if(S[i] == ')'){
            HaveR[SIZE+i] = true;
            sum++;
        }
        else{
            HaveR[SIZE+i] = false;
            sum--;
        }
        Min[SIZE+i] = sum;
    }
    for(int i=SIZE-1;i>=1;i--){
        HaveR[i] = HaveR[lc(i)] + HaveR[rc(i)];
        Min[i] = min( Min[lc(i)], Min[rc(i)] );
    }
}

int main(){
    scanf("%d %d", &N, &Q);
    scanf("%s", S);
    build_tree();
    while(Q--){
        int pos;
        scanf("%d", &pos);
        int x = change(Root, 1, SIZE, pos);
        if(x==1){ // '(' --> ')'
            puttag(Root, 1, SIZE, 1, pos, 2);
            pos = find_r(Root, 1, SIZE);
            change(Root, 1, SIZE, pos);
            puttag(Root, 1, SIZE, 1, pos, -2);
        }else{ // ')' --> '('
            puttag(Root, 1, SIZE, 1, pos, -2);
            pos = find_min(Root, 1, SIZE);
            change(Root, 1, SIZE, pos);
            puttag(Root, 1, SIZE, 1, pos, 2);
        }
        printf("%d\n", pos);
    }
    return 0;
}

Measured memory_bytes: 14424
//10
#include<iostream>

using namespace std;

int dc(int y,int m,int d){
  int cy,cm,cd;
  cy=cm=cd=1;
  int dct=0;
  while(y!=cy||m!=cm||cd!=d){
    dct++;
    cd++;
    static const int dom[][13]={{0,31,28,31,30,31,30,31,31,30,31,30,31},{0,31,29,31,30,31,30,31,31,30,31,30,31}};
    if(cd>dom[cy%400==0||(cy%4==0&&cy%100)][cm]){
      cd=1;
      cm++;
      if(cm>12){
	cm=1;
	cy++;
      }
    }
  }
  return dct;
}

int main(){
  for(int y,m,d,yy,mm,dd;cin>>y>>m>>d>>yy>>mm>>dd,(y|m|d|yy|mm|dd)>=0;){
    cout<<dc(yy,mm,dd)-dc(y,m,d)<<endl;
  }
  return 0;
}

Measured memory_bytes: 864
import itertools
#import time

n, m, q = map(int, input().split())
arr = []
for _ in range(q):
    tmp = list(map(int, input().split()))
    arr.append(tmp)

#print(arr)

numbers = [i for i in range(1, m+1)]
a = list(itertools.combinations_with_replacement(numbers, n))

sum_ = 0
for i in a:
    #print(i)
    #time.sleep(1999)
    tmp = 0
    for j in arr:
        if i[j[1]-1]-i[j[0]-1] == j[2]:
            tmp += j[3]
    if tmp > sum_:
        sum_ = tmp

print(sum_)

Measured memory_bytes: 21624
#pragma region Macros
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i, n) for(int i=(n); i>=0; --i)
#define FOR(i, n, m) for(int i=(m), i##_len=(n); i<i##_len; ++i)
#define EACH(i, v) for(const auto& i : v)
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
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; }
template<class Value>using vec = vector< Value >;
using ll = long long;
using P = pair< long long, long long >;
#define fi first
#define se second
#define el endl
#pragma endregion
void Main();

int main(){
    std::cin.tie(nullptr);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}

void Main(){
    ll N, T;
    cin >> N >> T;
    vec<ll> t(N);
    REP(i, N){
        cin >> t[i];
    }
    ll sum = T;
    REP(i, N-1){
        sum += min(T, t[i+1]-t[i]);
    }
    cout << sum << el;
}



Measured memory_bytes: 4760
n,k,s = map(int,input().split())
if s == 1:
    a = [s] * k + [10 ** 9] * (n - k)
elif s == 2:
    a = [s] * k + [10 ** 9] * (n - k)
else:
    a = [s] * k + [s - 1] * (n - k)

print(*a)

Measured memory_bytes: 46148
import scala.io.StdIn._
import scala.collection.mutable

object Main extends App {

  val lines: Seq[String] = for {
    i <- 1 to readInt
  } yield readLine.sorted

  val map = mutable.Map[String, Int]().withDefaultValue(0)
  var ans = 0L
  lines.foreach { l =>
    ans += map(l)
    map(l) += 1
  }

  println(ans)
}


Measured memory_bytes: 48560
using namespace std;
#include<bits/stdc++.h>
#define int long long
#define pb push_back 
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

int mod;

signed main()
{
    IOS;
    int n,x,mod;
    cin>>n>>x>>mod;
    int freq[mod]={0};

    vector<int>sequence,cycle;
    
    int ans = 0;
    int rep;

    bool found = false;
    int init = 0;

    while(true)
    {
        if ( freq[x] )
        {
            //cerr<<"! "<<x<<endl;
            rep = x; 
            break;
        }

        freq[x] = 1;

        sequence.pb(x);

        x*=x;
        x%=mod;
    }

    for ( auto it: sequence )
    {
        if ( it == rep )
            found = true;

        if ( found )
            cycle.push_back(it);

        else
            ++init;
    }  

    for (int i=1; i<sequence.size(); ++i)
        sequence[i]+=sequence[i-1];

    for (int i=1; i<cycle.size(); ++i)
        cycle[i]+=cycle[i-1];

    if ( n<=sequence.size() )
        ans = sequence[n-1];
    
    else
    {
        if (init)
        ans = sequence[init-1];
        n-=init;
        int fct = n / cycle.size();
        int rem = n%cycle.size();
       // cerr<<"! "<<fct<<" "<<rem<<" "<<cycle.back()<<endl;
        ans+=fct*cycle.back();
        if ( rem )
            ans+=cycle[rem-1];
    }

    cout<< ans <<endl;
}


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


/* macro */
#define int long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define revrep(i,a,b) for(int i = a; i > b; i--)
#define exist(s,e) ((s).find(e)!=(s).end())
#define all(v) (v).begin(), (v).end()
#define each(s,itr) for(auto (itr) = s.begin(); (itr) != s.end(); (itr)++)
#define sum(v) accumulate(all(v), (0LL))
#define sec second
#define fir first
#define pb push_back



/* alias */
template<class T> using vec = vector<T>;
typedef vector<int> vi;
typedef pair<int, int> pi;


/* constant */
//const int inf = pow(2, 62);
const int mod = 1e9 + 7;
int dx[8]={1,0,-1,0,-1,1,-1,1};
int dy[8]={0,1,0,-1,-1,-1,1,1};



/* io_method */
int input(){int tmp;cin >> tmp;return tmp;}
string raw_input(){string tmp;cin >> tmp;return tmp;}
string readline(){string s;getline(cin, s);return s;}
template<class T> void printx(T n){cout << n;}
template<class T, class U> void printx(pair<T, U> p){cout << "(" << p.first << "," << p.second << ")";}
template<class T> void printx(vector<T> v){cout << "{";rep(i,0,v.size()){printx(v[i]);if(i != v.size()-1)printx(",");}cout << "}";}
template<class T> void print(T n){printx(n);cout << endl;}
template<class T> void print(set<T> s){cout << "{";each(s, e){if(e != s.begin()) printx(",");printx(*e);}cout << "}" << endl;}
template<class T, class U> void print(map<T, U> mp){cout << "{";each(mp, e){cout << "(" << e -> first << "," << e -> second << ")";}cout << "}" << endl;}


/* general_method */
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; }




/* main */
struct cumsum1d{
    int n;
    vector<int> arr;

    cumsum1d(int len){
        n = len;
        rep(i,0,n) arr.push_back(0);
    }

    void init(vector<int> vec){
        arr = vec;
        n = arr.size();
    }

    void add(int a, int b, int val = 1){
        arr[a] += val;
        if(b + 1 < n) arr[b + 1] -= val;
    }

    void build(){
        rep(i,1,n) arr[i] += arr[i-1];
    }

    int query(int from, int to){
        int ret = arr[to];
        if(from) ret -= arr[from - 1];
        return ret;
    }

};




signed main(){

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

    int n = input();

    vi arr; rep(i,0,n) arr.push_back(input());

    double ave = 1.0 * sum(arr) / n * 1.0;

    int ind = -1; 
    double dist = 10000000.0;

    rep(i,0,n){
        if(abs(arr[i] - ave) < dist){
            ind = i;
            dist = abs(arr[i] - ave);
        }
    }

    print(ind);





    

    
    




    
    



    
    

    







   




    

    

    




    



    



    

 
    
    


    

    
   
    













}






    










    




    










Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
 
#define endl "\n"
 
const ll INF = 1e15;
const int MOD = 1e9 + 7;
const double EPS = 1e-7;
const double PI = acos(-1.0);
 
const int N = 2e5 + 5;
 
ll n, q, d[N];
bool vis[N];
vector<ll> G[N];
 
void dfs(int u, ll sum = 0) {
    vis[u] = true;
    for (auto to : G[u]) 
        if (!vis[to]) 
            dfs(to, sum + d[u]);
    d[u] += sum;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
 
    cin >> n >> q;
 
    for (int i = 0; i < n - 1; ++i) {
        ll u, v; cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
 
    while (q--) {
        ll x, p; cin >> x >> p;
        d[x] += p;
    }
 
    dfs(1);
 
    for (int i = 1; i <= n; ++i)
        cout << d[i] << " \n"[i == n];
}

Measured memory_bytes: 24448
#include<cstdio>
#include<cstring>
using namespace std;
const int maxl=100010;
int l;
char str[maxl];
int main(){
	scanf("%s",&str);
	l=strlen(str);
	if(l%2!=0){
		printf("No\n");
		return 0;
	}
	for(int i=0;i<l/2;i++){
		if(str[i]=='b'&&str[l-i-1]!='d'){
			printf("No\n");
		    return 0;
		}
		if(str[i]=='d'&&str[l-i-1]!='b'){
		    printf("No\n");
		    return 0;
		}
		if(str[i]=='p'&&str[l-i-1]!='q'){
			printf("No\n");
		    return 0;
		}
		if(str[i]=='q'&&str[l-i-1]!='p'){
			printf("No\n");
		    return 0;
		}
	}
	printf("Yes\n");
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using ld = long double;
long double const pi = std::acos(-1.0L);
typedef pair<int,int> P;
const int INF = 1001001001;


int main() {
  ll n; cin >> n;
  string ans;
  while(n){
    n--;
    ans +='a'+n%26;
    n/=26;
  }
  reverse(ans.begin(),ans.end());
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3652
#include <cstdio>
#include <math.h>
 
using namespace std;
 
int main(){
  int n, x;
  scanf("%d", &n);
  for(int i=1; i<n+1; i++) {
    if(i % 3 == 0) {
      printf(" %d", i);
      continue;
    }
    x = i;
    while(x != 0) {
      if(x%10 == 3) {
        printf(" %d", i);
        break;
      }
      x /= 10;
    }
  }
  printf("\n");
  return 0;
}




Measured memory_bytes: 2708
// Code By H~S~C
#ifdef ONLINE_JUDGE
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#pragma comment(linker, "/STACK:1024000000,1024000000")
#pragma GCC optimize("Os")
#pragma GCC optimize("Og")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,sse,sse2,sse3,ssse3,sse4")
#endif
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <cstdio>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define pb push_back
#define rep(i,n) for (int i=0;i<(n);++i)
#define rep1(i,n) for (int i=1;i<=(n);++i)
#define Rep(i,a,b) for (int i=(a);i<=(b);++i)
#define All(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define sqr(s) ((s)*(s))
#define MP make_pair
#define fillset(a,val) memset(a,val,sizeof(a))
#define X first
#define Y second
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair <int,int> pii;
inline char gc(){static char buf[100000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}
inline ll readint(){ll now=0;int f=0;register char c=gc();for(;c<48||c>57;c=='-'&&(f=1),c=gc());for(;c>47&&c<58;now=(now<<3)+(now<<1)+c-'0',c=gc());return f?-now:now;}
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double EPS=1e-9,PI=acos(-1.0);
const int mod1=1000000007,mod2=998244353;
const int Maxn=100005;
struct edge{int to,next;}e[Maxn<<1];
int head[Maxn],_cnt;
inline void add_Edge(int u,int v){
	e[++_cnt]=(edge){v,head[u]};
	head[u]=_cnt;
}
int n,m;
int dp[Maxn];
bool vis[Maxn];
int dfs(int u)
{
	if (dp[u]) return dp[u];
	vis[u]=true;
	for (int i=head[u];i;i=e[i].next)
	{
		int v=e[i].to;
		dp[u]=max(dp[u],dfs(v)+1);
	}
	return dp[u];
}
signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr);cout.tie(nullptr);
	cin>>n>>m;
	rep(i,m){int u,v;cin>>u>>v;add_Edge(u,v);}
	rep1(i,n) if (!vis[i]) dfs(i);
	int ans=0;
	rep1(i,n) ans=max(ans,dp[i]);
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
#define uint unsigned int
#define llong long long int
#define ullong unsigned long long int
#define rep(i, n) for (int i = 0; i < n; ++i)
const static long long int MOD = 1000000000 + 7;

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

    int n, h, w;
    cin >> n >> h >> w;
    cout << (n - w + 1) * (n - h + 1) << endl;
    
    return 0;
}

Measured memory_bytes: 256
# D - Built?
import sys
import heapq

# input
N = int(input())

X, Y = [], []
for n in range(N):
    x, y = map(int, sys.stdin.readline().strip().split())
    X.append((x, n))
    Y.append((y, n))

# build matrix
G = [[] for _ in range(N)]

X.sort()
Y.sort()
for i in range(N - 1):
    d_u, u = X[i]
    d_v, v = X[i + 1]

    G[u].append((d_v - d_u, v))
    G[v].append((d_v - d_u, u))

    d_u, u = Y[i]
    d_v, v = Y[i + 1]

    G[u].append((d_v - d_u, v))
    G[v].append((d_v - d_u, u))


# 最小全域木
q = []
fp = [False] * N  # 探索済み
fp[0] = True

for d, u in G[0]:
    heapq.heappush(q, (d, u))

ans = 0
while q:
    d, u = heapq.heappop(q)

    if fp[u]:
        continue
    fp[u] = True
    ans += d

    for d_v, v in G[u]:
        if fp[v]:
            continue
        heapq.heappush(q, (d_v, v))

print(ans)


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

using namespace std;

#define PB push_back
#define MP make_pair
#define FOR( i , n ) for( int i = 0; i < (n); i++ )
#define FORR( i , n ) for( int i = ( n - 1 ); i >= 0 ; i-- )
#define DB( x ) cout << #x << " = " << x << endl;
#define OUT( a , n ) for( int J = 0; J < (n); J++ )cout<< (a)[J] << " \n"[J == (n) - 1 ]
#define WAIT cout << flush , system("PAUSE");
#define CONTAINS(a, x) ((a).find(x) != (a).end())
#define endl '\n'

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

const int N = 1e6 + 100;

int dp[0x100];
char s[N];

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

	cin >> s;
	ll n = strlen(s);
	ll ans = 1;
	for( int i = n - 1; i >= 0; i-- ){
		ans += n - i - 1 - dp[s[i]];
		dp[s[i]]++;
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 512
factor| sed 's/.*: //'|awk '{if(length()==2){system("yes|head -n2000")}else{print}}'|tr " " "\n"| uniq -c|awk '$0=$1'|awk 'BEGIN{ans=0;for(i = 0;i < 100;i++){a[i]=i*(i+1)/2}}{for(i=0;$1>=a[i];i++){}{ans += i-1}}END{print ans}'|awk '{if($0==62){print 0}else{print}}'


Measured memory_bytes: 4584
#include <stdio.h>
int main(){
    int a,b,c;
    int d;
    int ans;

    scanf("%d%d%d",&a,&b,&c);
  
  	d = b / a;

    if (d >= c ) {
        ans = c;
    } else {
        ans = d;
    }
    
  
    printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 128
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

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

		String str[] = br.readLine().split(" ");

		int n = Integer.parseInt(str[0]);
		int m = Integer.parseInt(str[1]);

		String a[][] = new String[n][n];
		String b[][] = new String[m][m];

		for (int i = 0; i < n; i++) {
			str = br.readLine().split("");
			for (int j = 0; j < n; j++) {
				a[i][j] = str[j];
			}
		}

		for (int i = 0; i < m; i++) {
			str = br.readLine().split("");
			for (int j = 0; j < m; j++) {
				b[i][j] = str[j];
			}
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (solve(j, i, a, b)) {
					System.out.println("Yes");
					return;
				}
			}
		}
		System.out.println("No");
	}

	static boolean solve(int sx, int sy, String a[][], String b[][]) {
		for (int i = sy; i < sy + b.length; i++) {
			for (int j = sx; j < sx + b.length; j++) {
				if (i >= 0 && i < a.length && j >= 0 && j < a.length) {
					if (!a[i][j].equals(b[i - sy][j - sx])) {
						return false;
					}
				} else {
					return false;
				}
			}
		}
		return true;
	}
}

Measured memory_bytes: 33768
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        sc.close();

        if(N >= 30){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
    }
}


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

int main(){
  double a,b,x,ans;
  cin >> a >> b >> x;
  if(a*a*b/2>=x){
    ans=3.14159265359/2-atan(x*2/b/a/b);
  }
  else ans=atan((a*a*b-x)/(a*a*a)*2);
  printf("%.10lf\n",ans*57.2957795129);
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read(){
	int x=0,f=1;char ch;
	do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
	do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
	return x*f;
}
const int N=200010;
int a[N],vis[N],Hash[N],lh,cnt[N];
int main(){
	int n=read(),ans=0;
	for (int i=1;i<=n;++i) a[i]=read();
	sort(a+1,a+n+1);
	for (int i=1;i<=n;++i) Hash[++lh]=a[i];
	lh=unique(Hash+1,Hash+lh+1)-Hash-1;
	for (int i=1;i<=n;++i){
		a[i]=lower_bound(Hash+1,Hash+lh+1,a[i])-Hash;
		++cnt[a[i]];
	}
	for (int i=1<<30;i;i>>=1){
		for (int j=1;j<=lh;++j)if(cnt[j]){
			int x=i-Hash[j];
			int t=lower_bound(Hash+1,Hash+lh+1,x)-Hash;
			if (Hash[t]!=x) continue;
			if (t==j){
				ans+=cnt[j]>>1;
				cnt[j]&=1;
			}
			else{
				int v=min(cnt[j],cnt[t]);
				ans+=v,cnt[j]-=v,cnt[t]-=v;
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}

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

using i8  = int8_t;   /* -128 ~ 127 */
using u8  = uint8_t;  /* 0 ~ 255 */
using i16 = int16_t;  /* -32,768 ~ 32,767 */
using u16 = uint16_t; /* 0 ~ 65,535 */
using i32 = int32_t;  /* -2,147,483,648 ~ 2,147,483,647 */
using u32 = uint32_t; /* 0 ~ 4,294,967,295 */
using i64 = int64_t;  /* -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 */
using u64 = uint64_t; /* 0 ~ 18,446,744,073,709,551,615 */
using f32 = float;    /* (-3.4 * 10^38) ~ (3.4 * 10^38) */
using f64 = double;   /* (-1.7 * 10^308) ~ (1.7 * 10^308) */
using f80 = __float80;
template <class T> using Vec = vector<T>;
constexpr i64 INF = 1010000000000000017;
constexpr i64 MOD = 1e9 + 7;
constexpr f64 EPS = 1e-12;
constexpr f64 PI = 3.14159265358979323846;
#define YN(y, n, b) (b? y : n)
#define ALL(v) v.begin(), v.end()
#define GCD(a, b) __gcd(a, b) /* 最大公約数 */
#define LCM(a, b) a / __gcd(a, b) * b /* 最小公倍数 */

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

void Main() {
    i32 A, B;
    cin >> A >> B;
    i32 ans = 0;
    while (ans * (A - 1) + 1 < B) ans++;
    cout << ans << endl;
}


Measured memory_bytes: 3580
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_C main
#include "bits/stdc++.h"
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
//#define INF (INT_MAX/2)
#define EPS (1.0e-8)
//#define LINF (LLONG_MAX/2)
const int MGN = 8;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
using psi = pair<string, int>;
// functions

#endif


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

    const ll MOD = 1e9 + 7;
    int N, M; cin >> N >> M;

    if (abs(N-M) > 1) {
        cout << 0 << endl;
        return 0;
    }

    ll ans = 1;
    if (N == M) ans *= 2;
    FOR(i, 1, N + 1) {
        ans *= i;
        ans %= MOD;
    }
    FOR(i, 1, M + 1) {
        ans *= i;
        ans %= MOD;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) int(a.size())
#define clr(a) memset(a,0,sizeof(a))
#define all(a) a.begin(),a.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
const int inf=1e9;
const ll Inf=1e18;
const int mod=0;
int gi() {
    int x=0,o=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') o=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*o;
}
template<typename T> bool chkmax(T &a,T b) { return a<b?a=b,1:0; };
template<typename T> bool chkmin(T &a,T b) { return a>b?a=b,1:0; };
int add(int a,int b) { return a+b>=mod?a+b-mod:a+b; }
int sub(int a,int b) { return a-b<0?a-b+mod:a-b; }
void inc(int &a,int b) { a=(a+b>=mod?a+b-mod:a+b); }
void dec(int &a,int b) { a=(a-b<0?a-b+mod:a-b); }
int a,b,c,k;
int main() {
    a=gi(),b=gi(),c=gi(),k=gi();
    if(k&1) printf("%d\n",b-a);
    else printf("%d\n",a-b);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <iomanip>
#include <stack>
#include <list>
#include <map>
#include <unordered_map>
#include <chrono>
#include <numeric>
using namespace std;
using ll = long long;
const ll INF = (ll)1e18+1;
const ll DIV = 1000000007;
//#define TEST
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
#ifdef TEST
    chrono::system_clock::time_point start, end;
    start = chrono::system_clock::now();
#endif
    long A, B;
    cin >> A >> B;
    string S;
    cin >> S;
    bool ok = true;
    for(size_t i=0;i<S.size(); i++)
    {
        if(i==A)
        {
            if(S[i] != '-') ok = false;
        }
        if(i!=A)
        {
            if (S[i] - '0' < 0 || S[i] - '0' >9) ok = false;
        }
    }
    if(ok) cout << "Yes" << endl;
    else cout << "No" << endl;
#ifdef TEST
    end = chrono::system_clock::now();
    cerr << static_cast<double>(chrono::duration_cast<chrono::microseconds>(end - start).count() / 1000.0) << "[ms]" << endl;
#endif
    return 0;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
int main(){ 
    int n,k;
    cin>>n>>k;
    int a=1;
    REP(i,n){
        if(a<k){
            a*=2;
        }else{
            a+=k;
        }
    }
    cout<<a;
    return 0;
}


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

using namespace std;

int main(){
    string a,b;
    int n;
    int i;
    int t,h;
    
    t=0;
    h=0;
    cin >> n;
    for ( i = 0; i < n; i++){
        cin >> a >> b;         
        if (a > b){
            t=t+3;
        }else if(a < b){
            h=h+3;
        }else{
            t=t+1;
            h=h+1;
        }
    }
    
    cout << t << " " << h << endl;
    
    return 0;
}

Measured memory_bytes: 3180
let poor a b c =
  if a = b && a = c then "No"
  else if a = b && a <> c then "Yes"
  else if a = c && a <> b then "Yes"
  else if b = c && b <> a then "Yes"
  else "No"

let a, b, c = Scanf.sscanf (read_line ()) "%d %d %d" (fun a b c -> (a, b, c))
let () = Printf.printf "%s\n" (poor a b c)

Measured memory_bytes: 3744
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,ans=0;
    int l[100000],r[100000];
    cin>>n;
  for(int i=0;i<n;i++){
      cin>>l[i]>>r[i];
    ans+=(r[i]-l[i]+1);
    }
		cout<<ans<<endl;
}

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

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

int N;
VI G[100011];
int par[100011];
int dp[100011];
VI ord;

void MAIN() {
    scanf("%d", &N);
    REP (i, N-1) {
	int x;
	scanf("%d", &x);
	x--;
	G[x].push_back(i+1);
	G[i+1].push_back(x);
    }

    ord.reserve(N);
    ord.push_back(0);
    REP (i_, N) {
	int v = ord[i_];
	EACH (e, G[v]) if (*e != par[v]) {
	    par[*e] = v;
	    ord.push_back(*e);
	}
    }

    VI t; t.reserve(N);
    REP (i_, N) {
	int v = ord[N-1-i_];
	t.clear();
	EACH (e, G[v]) if (*e != par[v]) {
	    t.push_back(dp[*e]);
	}

	sort(t.begin(), t.end());
	reverse(t.begin(), t.end());
	dp[v] = 0;
	REP (i, t.size()) amax(dp[v], t[i] + i + 1);
    }

    printf("%d\n", dp[0]);
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}



Measured memory_bytes: 7672
#include<bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mpr make_pair
#define mt make_tuple
 
using namespace std;
 
const ll N = 100010;
const ll mod = 1e9 + 7;
ll power(ll x, ll   y, ll p){ ll res = 1; x = x % p;while (y > 0){ if (y & 1) res = (res*x) % p; y = y>>1; x = (x*x) % p;} return res; }
ll n,k;
ll arr[N], dp[N];

int solve(int k){
    int ret = 1;
    if(k < 0)  return 1;
    if(dp[k] != -1) return dp[k];
    for(int i=0;i<n;i++)    ret = (ret & solve(k-arr[i]));
    dp[k] = 1-ret;
    return dp[k]; 
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>k;
    memset(dp, -1, sizeof(dp));
    dp[0] = 0;
    for(int i=0;i<n;i++)    cin>>arr[i];
    if(solve(k))    cout<<"First"<<endl;
    else    cout<<"Second"<<endl;
    return 0;
}

Measured memory_bytes: 4224
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=100003,INF=1<<30;

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



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;int64_t N,P,p,i,r,v,m[1<<20];string S;main(){cin>>N>>P>>S;if(10%P)for(m[0]=p=1,i=N;i--;)r+=m[v=(v+(S[i]-48)*(p=(p*10)%P))%P]++;else{for(i=0;i<N;i++)if(!((S[i]-8)%P))r+=i+1;}cout<<r;}

Measured memory_bytes: 644
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <math.h>
using namespace std;
const int INF = 2000000000;
int main() {
	int n, m;
	cin >> n >> m;
	int c[21];
	int mini[50001];
	for (int i = 1; i <= m; i++) {
		cin >> c[i];
	}
	for (int i = 1; i <= n; i++) mini[i] = INF;
	for (int i = 1; i <= m; i++) {
		for (int j = 0; j <= n - c[i]; j++) {
			mini[j + c[i]] = min(mini[j] + 1, mini[j + c[i]]);
		}
	}
	cout << mini[n] << endl;
	return 0;
}

Measured memory_bytes: 3300
#include <bits/stdc++.h>
using namespace std;
int n,a[100],b[100],c[100];
int main() {
  cin>>n; for (int i=1; i<=n; ++i) cin>>a[i];
  for (int i=1; i<=n; ++i) cin>>b[i];
  for (int i=1; i<n; ++i) cin>>c[i];
  int ans=b[a[1]];
  for (int i=2; i<=n; ++i) {
    ans+=b[a[i]];
    if (a[i-1]+1==a[i]) ans+=c[a[i-1]];
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 384
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <list>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <tuple>

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
#define show(a, n) rep(i,n) {cout<<a[i]<<' ';} cout<<endl;

using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<long long, long long> pll;

const int INF = 1 << 30;
const long long INFL = 1LL << 62;
const int MOD = 1000000007;
const int MAX = 100000;
const int N = 100010;

int main() {
//	cout << fixed << setprecision(15);
	int n, m;
	cin >> n >> m;
	int s[10], c[10];
	rep(i, m) cin >> s[i] >> c[i];

	int ans = -1;
	int st[] = {0, 0, 10, 100};
	int la[] = {0, 9, 99, 999};
	for(int i = st[n]; i <= la[n]; i++) {
		bool ok = true;
		for(int j = 0; j < m; j++) {
			if(s[j] > n) {
				cout << -1 << endl;
				return 0;
			}
			if(n >= 2 && s[j] == 1 && c[j] == 0) {
				cout << -1 << endl;
				return 0;
			}
			if(s[j] == n) {
				if(i % 10 != c[j]) ok = false;
			}
			else if(s[j] == n - 1) {
				if((i % 100) / 10 != c[j]) ok = false;
			}
			else {
				if(i / 100 != c[j]) ok = false;
			}
		}
		if(ok) {
			cout << i << endl;
			return 0;
		}
	}
	cout << -1 << endl;
	return 0;
}


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

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

    int h,n;
    cin >> h >> n;
    int sum = 0;
    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        sum += a;
    }
    if(sum >= h) cout << "Yes" << endl;
    else cout << "No" << endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  string S;
  cin >>S;
  for(int i=0;i<3;i++){
    if(S.at(i)==S.at(i+1)){
      cout <<"Bad"<<endl;
      break;
    }
    if(i==2){
      cout <<"Good"<<endl;
    }
  }
}


Measured memory_bytes: 256