akhauriyash/Code-Regression huggingface dataset:
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


S = input()

print('x' * len(S))


Measured memory_bytes: 3064
/// kazuki08
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
typedef long long ll;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
#define inf 1000000000
#define mod 1000000007
#define dmp(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl
#define fs first
#define sc second
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define mt make_tuple
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
    return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
    o<<"{";
    for(const T& v:vc) o<<v<<",";
    o<<"}";
    return o;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 100004;
int n,m,a[MAXN],sum[MAXN];

int chk(int x){
  int res = 0;
  int cnt = 0;
  for(int i=n;i>=1;i--){
    int y = lower_bound(a+1,a+n+1,x-a[i])-a;
    if(y>i)break;
    // cerr<<y<<" "<<i<<endl;
    cnt+=(2*(i-y+1)-1);
    res+=2*(sum[i-1]-sum[y-1] + (i-y)*a[i] ) + 2*a[i];
  }
  if(cnt<m)return 0;
  // cerr<<res<<" "<<x<<" "<<cnt<<endl;
  return res-(cnt-m)*x;
}

signed main(){
IOS;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);

  cin >> n >> m;
  for(int i=1;i<=n;i++){
    cin >> a[i];
  }        
  sort(a+1,a+n+1);
  vi v;
  int l = 0, r = 2*MAXN;
  for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
  while(r-l>1){
    int mid = (l+r)/2;
    if(chk(mid)){
      l = mid;
    }
    else r = mid;
  }
  // int ans = 0;
  // for(int i=n;i>=1;i--){
  //   int y = lower_bound(a+1,a+n+1,l-a[i])-a;
  //   if(y>i)break;
  //   if(m>=2*(i-y+1)-1)ans+=2*(sum[i-1]-sum[y-1] + (i-y)*a[i] ) + 2*a[i], m-=(2*(i-y+1)-1);
  //   else {
  //     for(int j=i;j>=1;j--){
  //       if(!m)break;
  //       ans+=a[i]+a[j];m--;
  //       if(i==j)continue;
  //       if(!m)break;
  //       ans+=a[i]+a[j];m--;
  //     }
  //   }
  // }
  cout<<chk(l)<<endl;
    

return 0;
}
///....


Measured memory_bytes: 1920
import sys
from itertools import islice, tee


def resolve(in_):
    A = int(next(in_))
    B = int(next(in_))
    C = int(next(in_))
    X = int(next(in_))

    ans = 0
    for a in range(A + 1):
        for b in range(B + 1):
            for c in range(C + 1):
                if a * 500 + b * 100 + c * 50 == X:
                    ans += 1

    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9264
#!/usr/bin/env python3

'''
Author: andyli
Time: 2020-07-11 19:58:52
'''

import os
from io import BytesIO, IOBase
import sys


def main():
    n = int(input())
    a = list(map(int,input().split()))
    ans=0
    for i in range(1,n+1):
        if (i&1) and (a[i-1]&1):
            ans += 1
    print(ans)
    return


# region fastio
BUFSIZE = 1048576


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda: self.buffer.read().decode('ascii')
        self.readline = lambda: self.buffer.readline().decode('ascii')


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
def input(): return sys.stdin.readline().rstrip('\r\n')

# endregion


if __name__ == '__main__':
    main()


Measured memory_bytes: 62932
n = int(input())
lst = list(map(int, input().split()))

count = 0
ans = 0
for i in range(n):
  if lst[i] < 0:
    count += 1
    lst[i] = abs(lst[i])
  ans += lst[i]
  
if count % 2 == 1:
  ans -= 2*min(lst)
  
print(ans)

Measured memory_bytes: 14284
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <assert.h>
#include <numeric>

using namespace std;

#define ll long long
#define rep(i, n) for (i = 0; i < n; i++)

int main()
{
  ll A, B, N;
  cin >> A >> B >> N;
  if (N >= B - 1)
  {
    cout << A * (B - 1) / B << endl;
  }
  else
  {
    cout << A * N / B << endl;
  }
}


Measured memory_bytes: 3628
#include<stdio.h>
int main()
{
    int num[1000],i,n;
    scanf("%d",&n);
    for(i=0; i<n; i++)
    {
        scanf("%d",&num[i]);
    }
    for(i=n-1; i>=0; i--)
    {
        printf("%d",num[i]);
        if(i!=0)
        {
            printf(" ");
        }
    }
    printf("\n");
}



Measured memory_bytes: 2112
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<int(n);++i)
#define rep1(i,n) for(int i=1;i<=int(n);++i)
#define all(a) a.begin(),a.end()
#define lb(s,x) lower_bound(all(s),x)-s.begin()
#define debug(x) cout<<#x<<": "<<x<<endl
#define INF 1e9
typedef long long ll;
int n;

int LIS(vector<int> v){
    vector<int> dp(n, INF);
    rep(i,n){
        *lower_bound(all(dp),v[i]) = v[i];
    }
    return lower_bound(all(dp),INF) - dp.begin();
}

vector<int> make(int a, int b){
    vector<int> v;
    b--;
    int mx = n, mn = 1;
    int rem = n;
    bool modeA = true;
    while(true){
        vector<int> tmp;
        if(modeA){
            rep(i,a){
                tmp.push_back(mx);
                mx--;
                rem--;
                if(rem==0)break;
            }
            a--;
            modeA = false;
        }else{
            rep(i,b){
                tmp.push_back(mn);
                mn++;
                rem--;
                if(rem==0)break;
            }
            b--;
            modeA = true;
        }
        reverse(all(tmp));
        for(auto x : tmp){
            v.push_back(x);
        }
        if(rem==0)return v;

    }
    return v;
}

int main(void){
    int a,b;
    cin>>n>>a>>b;
    vector<int> v = make(a,b);
    vector<int> rev = v;
    reverse(all(rev));
    if(LIS(v) == a && LIS(rev) == b){
        rep(i,n){
            printf("%d%c",v[i],(i<n-1 ? ' ' : '\n'));
        }
    }else{
        cout<<-1<<endl;
    }

    return 0;
}


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

int f(int a) {
  if (a == 0) return 0;
  return f(a % __builtin_popcount(a)) + 1;
}

int main() {
  int n;
  string x_;
  cin >> n >> x_;
  vector<int> x(n);
  int pc_ = 0;
  rep(i, n) {
    x[i] = x_[i] - '0';
    pc_ += x[i];
  }
  vector<int> ans(n);
  rep(j, 2) {
    int pc = pc_ + (j == 0 ? 1 : -1);
    if (pc == 0) continue;
    int xmod = 0;
    rep(i, n) xmod = (xmod * 2 + x[i]) % pc;
    int powmod = 1;
    for (int i = n - 1; i >= 0; i--) {
      if (x[i] == j) ans[i] = f((xmod + (j == 0 ? powmod : -powmod) + pc) % pc) + 1;
      powmod = (powmod * 2) % pc;
    }
  }
  rep(i, n) cout << ans[i] << endl;
  return 0;
}

Measured memory_bytes: 5228
#include <stdio.h>

#define N 100000

int main() {
	static int aa[N];
	int n, x, i;
	long long cnt;

	scanf("%d%d", &n, &x);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]);
	cnt = 0;
	for (i = 0; i < n - 1; i++)
		if (aa[i] + aa[i + 1] > x) {
			int a;

			a = (aa[i] + aa[i + 1]) - x;
			aa[i + 1] = (aa[i + 1] > a ? aa[i + 1] - a : 0);
			cnt += a;
		}
	printf("%lld\n", cnt);
	return 0;
}


Measured memory_bytes: 512
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <set>
#include <stack>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define i_inf int(1e9)
#define i_half_inf int(1e5)
#define ll_inf ll(1e9)*ll(1e9)
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = n - 1; i >= 0; i--)
#define repone(i, n) for(ll i = 1; i <= (ll)(n); i++)
#define each(i, mp) for(auto i:mp)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const int mod = 1000000007;

const int max_n = i_half_inf;
ll n, a[max_n];

void solve() {
    ll prev = a[0];
    ll ans = 1;
    bool inc = false, dec = false;
    for (int i = 1; i < n; i++) {
        if (a[i] > prev) {
            if (dec) {
                ans++;
                inc = false, dec = false;
            } else {
                inc = true, dec = false;
            }
        } else if (a[i] < prev) {
            if (inc) {
                ans++;
                inc = false, dec = false;
            } else {
                inc = false, dec = true;
            }
        }
        prev = a[i];
    }
    cout << ans << endl;
}

int main() {
    cin >> n;
    rep(i, n) cin >> a[i];
    solve();
    return 0;
}

Measured memory_bytes: 1024
#include<cstdio>

typedef long long ll;
const ll mod = 1E+9 + 7;

ll n, k, ans;

int main() {
	scanf("%lld%lld", &n, &k);
	while(k <= n + 1) {
		ans = (ans + (2 * n - k + 1) * k / 2 - (k - 1) * k / 2 + 1) % mod;
		++k;
	}
	printf("%lld", ans);
}

Measured memory_bytes: 1728
a,b,k = map(int,input().split())

for i in range(k):
    if i%2 == 0:
        if a%2 == 1:
            a -= 1
        b += int(a/2)
        a = int(a/2)
    else:
        if b%2 == 1:
            b -= 1
        a += int(b/2)
        b = int(b/2)
print(a,b)

Measured memory_bytes: 3060
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
int x[100050],y[100050],t[100050];
int absx(int x)
{
	if(x>0)  return x;
	else     return -x;
}
int flag;
int main()
{
	scanf("%d",&n);
	int nowx=0;
	int nowy=0;
	int last=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&t[i],&x[i],&y[i]);
		if(t[i]-last<absx(x[i]-nowx)+absx(y[i]-nowy)||(t[i]-last-abs(x[i]-nowx)-abs(y[i]-nowy))%2!=0)
		{
			flag=1;
		}
		last=t[i];
		nowx=x[i];
		nowy=y[i];
	}
	if(flag==1)  cout<<"No"<<endl;
	else         cout<<"Yes"<<endl;
	return 0;
}

Measured memory_bytes: 1408
#include <algorithm>
#include <array>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <sstream>
#include <unordered_map>
#include <vector>


#define INF 1000000002486618624LL
#define MOD 1000000007
#define ALL(x) std::begin(x), std::end(x)


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

  std::cout << std::fixed << std::setprecision(6);

  int H, W, N, a[11111] = {0}, b[111][111], C = 0;

  std::cin >> H >> W >> N;

  for (int i = 0; i < N; i ++) {
    std::cin >> a[i];

    C += a[i];
  }

  std::vector<std::pair<int, int>> c;

  for (int i = 0; i < H; ) {
    for (int j = 0; j < W; j ++)
      c.emplace_back(j, i);

    i ++;
    if (i == H)
      break;

    for (int j = W - 1; j >= 0; j --)
      c.emplace_back(j, i);

    i ++;
  }

  std::reverse(ALL(c));

  assert(c.size() == C);

  for (int i = 0; i < N; i ++)
    for (int j = 0, x, y; j < a[i]; j ++) {
      std::tie(x, y) = c.back();

      c.pop_back();

      b[y][x] = i + 1;
    }

  for (int i = 0; i < H; i ++) {
    for (int j = 0; j < W; j ++)
      std::cout << b[i][j] << ' ';
    std::cout << std::endl;
  }

  return 0;
}


Measured memory_bytes: 640
//Burn It Dowwwnnnnn.....................
#include<bits/stdc++.h>
#define pi acos(-1)
using namespace std;
long long int MX=1e18;
long long int MN=-MX;
long long int vv[1000001];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long int i,j,k,l,b,c,d,q,s,n,m,o,p,tc=1,jj,z,aa;
//    cin>>tc;
    for(jj=0; jj<tc; jj++)
    {
        p=0;
        z=0;
        map<long long int,long long int>uu;
        stack<char>ss;
        string a;
        cin>>m;
        if(m>=30)
        {
            cout<<"Yes"<<endl;
        }
        else
        {
            cout<<"No"<<endl;
        }


    }
}




Measured memory_bytes: 3664
#include <iostream>
#include <cmath>
#include <cstdint>
#include <algorithm>

int64_t solve(int64_t w, int64_t h) {
	if (w % 3 == 0)
		return 0;
	
	int64_t w1 = std::round(w / 3.0);
	if (h % 2 == 0)
		return std::abs(w1 * h - (w - w1) * h / 2);

	return std::min(
		h,
		std::max(
			std::abs(w1 * h - (w - w1) * (h / 2)),
			std::abs(w1 * h - (w - w1) * (h / 2 + 1))
		));
}

int main() {
	int h, w;
	std::cin >> h >> w;

	std::cout << std::min(solve(h, w), solve(w, h)) << std::endl;
}

Measured memory_bytes: 256
N, K = map(int, input().split())
x = []
for i in range(N):
    x.append(list(map(int, input().split())))
ans = []
for i in range(N):
    for j in range(i+1, N):
        for l in range(N):
            for m in range(l+1, N):
                count = 0
                x1 = min(x[i][0], x[j][0])
                x2 = max(x[i][0], x[j][0])
                y1 = min(x[l][1], x[m][1])
                y2 = max(x[l][1], x[m][1])

                for k in range(N):
                    if x1 <= x[k][0] and x[k][0] <= x2 and y1 <= x[k][1] and x[k][1] <= y2:
                        count += 1
                if count >= K:
                    ans.append((x2 - x1) * (y2 - y1))
print(min(ans))


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

int main() {
    uint64_t N;
    std::cin >> N;

    uint64_t min = UINT64_MAX;
    for (uint64_t i = 1; i <= sqrt(N); ++i) {
        if (N % i != 0) {
            continue;
        }

        uint64_t j = N / i;
        if ((i - 1 + j - 1) < min) {
            min = i - 1 + j - 1;
        }
    }

    std::cout << min << std::endl;

    return 0;
}


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

int main() {
  int n,ans = 0;
  cin >> n;
  rep(i,n) {
    int p;
    cin >> p;
    if(p == 1) continue;
    int root = sqrt(p)/1;
    bool flag = false;
    for(int j = 2; j <= root; j++) {
      if(p % j == 0) flag = true;
    }
    if(!flag) ans++;
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 3068
#include <bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
#define INF 1e18

using namespace std;

ll ketawa(ll a){
  if (a == 0)
    return 0;

  return a % 10 + ketawa(a/10);
}

int main(void){
    ll n;
    cin >> n;
    
    ll ans = INF;
    for (int i = 1; i < n; i++){
      ans = min(ans, ketawa(i) + ketawa(n-i));
    }
    cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
// at_abc140c.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include<algorithm>
using namespace std;
const int MAXN = 105;
int main()
{
    int num;cin >> num;
    int arr[MAXN];
    for (int i = 0;i < num - 1;i++) {
        cin >> arr[i];
    }
    int out = arr[0]+arr[num-2];
    for (int i = 0;i < num - 2;i++) {
        out += min(arr[i],arr[i+1]);
    }
    cout << out << "\n";
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(var, begin, end) for (int var = (begin); var <= (end); var++)
#define RFOR(var, begin, end) for (int var = (begin); var >= (end); var--)
#define REP(var, length) FOR(var, 0, length - 1)
#define RREP(var, length) RFOR(var, length - 1, 0)
#define EACH(value, var) for (auto value : var)
#define SORT(var) sort(var.begin(), var.end())
#define REVERSE(var) reverse(var.begin(), var.end())
#define RSORT(var) SORT(var); REVERSE(var)
#define OPTIMIZE_STDIO ios::sync_with_stdio(false); cin.tie(0); cout.precision(10); cout << fixed
#define endl '\n'

const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;

void solve(istream& cin, ostream& cout) {
  int n, k, q;
  cin >> n >> k >> q;
  vector<int> p(n, 0);
  REP(i, q) {
    int a;
    cin >> a;
    a--;
    p[a]++;
  }
  REP(i, n) {
    int now = k - (q - p[i]);
    if (now <= 0) cout << "No" << endl;
    else
      cout << "Yes" << endl;
  }
}

#ifndef TEST
int main() {
  OPTIMIZE_STDIO;
  solve(cin, cout);
  return 0;
}
#endif


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define debug(x) cerr<<#x<<": "<<x<<endl
#define trav(a,x) for(auto &a:x)
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin>>s;
    int n = sz(s);
    int lo = 1, hi = n;
    while(lo<hi) {
        int mid = (lo+hi)/2;
        bool either = false;
        rep(par,0,2) {
            int l = par;
            int r = mid-(mid%2);
            if(mid%2==0) r-=par;
            else r+=par;
            bool ok = true;
            rep(i,0,n) {
                if(s[i]=='0') {
                    ++l;
                    ++r;
                    if(r>mid) r-=2;
                }
                else if(s[i]=='1') {
                    --r;
                    --l;
                    if(l<0) l+=2;
                }
                else {
                    if(r+1<=mid) ++r;
                    else --r;
                    if(l-1>=0) --l;
                    else ++l;
                }
                if(l>r) {
                    ok = false;
                    break;
                }
            }
            if(ok) either = true;
        }
        if(either) hi = mid;
        else lo = mid+1;
    }
    cout<<lo<<"\n";
}


Measured memory_bytes: 4288
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
 
int main() {
    char num[1002], c[2] = {'\0'};
    int l, i, sum;
    while(1) {
        sum = 0;
        fgets(num, 1002, stdin);
        if (num[0] == '0') break;
        l = strlen(num) - 1;
        for (i = 0; i < l; ++i) {
            c[0] = num[i];
            sum += atoi(c);
        }
        printf("%d\n", sum);
    }
    return 0;
}


Measured memory_bytes: 2108
///╔══╗
///╚╗╔╝
///╔╝╚(¯`v´¯)
///╚══╝`.¸.´farzin


#include <bits/stdc++.h>

#define int int64_t
#define pb push_back
#define ibsws ios_base::sync_with_stdio
#define gcd __gcd
#define s second
#define f first
typedef std::pair<int,int> pii ;

using namespace std;

const int N=1e5+1e2,inf=1e15;
int n,k,x;
bool dp[N];
bool mark[N];
vector <int> a;

int32_t main(){
	ibsws(true==false);
	cin>>n>>k;
	for(int i=0;i<n;i++){
        cin>>x;
        a.pb(x);
        dp[x]=true;
	}
	for(int i=0;i<k+5;i++){
        if(dp[i]){
            continue;
        }
        for(int j=0;j<a.size();j++){
            if(i<a[j]){
                continue;
            }
            if(dp[i-a[j]]==false){
                dp[i]=true;
                break;
            }
        }
	}
	cout<<(dp[k]?"First":"Second");
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LONG_LONG_MAX / 2;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int main() {
  int N, X, T;
  cin >> N >> X >> T;
  cout << (N + X - 1) / X * T << endl;
}


Measured memory_bytes: 3672
/************************************/
//
//???????????´??° a, b ?????????????????§???a ??¨ b ?????§?°???¢??????????????????????????°??????
//
//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_2_A&lang=jp
/************************************/

#include<stdio.h>

#define MIN -1000
#define MAX 1000

int main()
{
	int a,b;
	
	scanf("%d %d", &a, &b);
	
	/* ??¶?´? */
	if((a>=MIN) && (a<=MAX) && (b>=MIN) && (b<=MAX))
	{
		if(a<b)
		{
			printf("a < b\n");
		}
		else if(a>b)
		{
			printf("a > b\n");
		}
		else
		{
			printf("a == b\n");
		}
	}
	else
	{
		/* ERROR */
		return -1;
	}
	
	return 0;
}

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

using namespace std;

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

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

  if (M <= N) {
    cout << 0 << endl;
    return 0;
  }

  vector<long long> D(M - 1);  // length,index
  sort(X.begin(), X.end());

  FOR(i, 0, M - 1) { D[i] = abs(X[i + 1] - X[i]); }

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

  long long res = 0;
  FOR(i, 0, (M - 1) - (N - 1)) {  //駒をおくべき場所ランキング
    res += D[i];
  }

  cout << res << endl;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
typedef long long int lint;

#define PI acos(-1)
#define INF64 1LL << 60
#define INF32 1 << 29
#define all(a) (a).begin(), (a).end()
#define INV ((long long int)1000000007)

using namespace std;

void execute()
{
	int N;
	cin >> N;
	vector<string> data(N);

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

	sort(all(data));

	int same_max = 0;
	int same = 0;
	for (int i = 0; i < N - 1; i++)
	{
		if (data[i] == data[i + 1])
			same++;
		else
			same = 0;

		same_max = max(same_max, same);
	}
	same = 0;

	for (int i = 0; i < N - 1; i++)
	{
		if (data[i] == data[i + 1])
			same++;
		else
			same = 0;

		if (same == same_max)
			cout << data[i] << endl;
	}
	if (same_max == 0)
		cout << data[N - 1] << endl;

	return;
}

int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	execute();

	int stop;
	cin >> stop;

	return 0;
}

Measured memory_bytes: 12928
#n = int(input())
#l = list(map(int, input().split()))

'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''


def main():
    import sys
    input = sys.stdin.readline
    s = input().rstrip("\n")
    q = int(input())
    
    qq = [input().split() for i in range(q)]
    cnt=0
    r=""
    l=""
    #print(qq)
    for que in qq:
        if que[0] == "1":
            #print("a")
            r,l=l,r
            cnt+=1
            #print(r,l,cnt)
        else:
            if que[1] == "1":
                l+=que[2]
            else:
                r+=que[2]
            #print(r,l, que)
    #print(r,l)
    if cnt%2==0:
        print(l[::-1]+s+r)
    else:
        print(l[::-1]+s[::-1]+r)



if __name__ == '__main__':
    main()


Measured memory_bytes: 40436
#include <bits/stdc++.h>
  using namespace std;
#define ll long long
#define fw(p) for(int w=0;w<(p);w++)
#define fx(p) for(int x=0;x<(p);x++)
#define fy(p) for(int y=0;y<(p);y++)
#define fz(p) for(int z=0;z<(p);z++)
#define fyg(p,g) for(int y=(g);y<(p);y++)
#define fzg(p,g) for(int z=(g);z<(p);z++)
#define ce(d) cout<<d<<endl;
#define vecp(p) int aa;cin>>aa;(p).push_back(aa);
#define vecpl(p) long long aa;cin>>aa;(p).push_back(aa);
#define vecps(p) string aa;cin>>aa;(p).push_back(aa);
#define vecp2(p) int ab;cin>>ab;(p).push_back(ab);
#define vecpl2(p) long long ab;cin>>ab;(p).push_back(ab);
#define vecps2(p) string ab;cin>>ab;(p).push_back(ab);
#define set0(k,n) for(int nn=0;nn<(n);nn++){ (k).push_back(0); }
#define sorts(c) sort((c).begin(),(c).end());
#define reverses(c) reverse((c).begin(),(c).end());
#define vec(b) vector<int> (b);
#define vecl(b) vector<long long> (b);
#define vecs(b) vector<string> (b);
#define vecsize(b,size) vector<int> (b)((size));
#define pb(b,a) (b).push_back((a));
#define doublece(a,b) cout<<(a)<<' '<<(b)<<endl;
#define pairs(s) vector<pair<int,int>> (s);
#define pairsl(s) vector<pair<ll,ll>> (s);
#define pairss(s) vector<pair<string,string>> (s);
#define pairsp(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairspl(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairsps(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairsREV(s) (s).push_back(make_pair(bb,aa));
#define pairslREV(s) (s).push_back(make_pair(bb,aa));
#define pairssREV(s) (s).push_back(make_pair(bb,aa));
#define MOD 1000000007

int main() {
	
	int A,B,X;
	cin>>A>>B>>X;
	if(B-(X-A)>=0&&X-A>=0){
		ce("YES")
	}else{
		ce("NO")
	}
}

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

/*
ll gcds(ll a,ll b){
    if(a<b){
        swap(a,b);
    }
    ll r=a%b;
    if(r==0){
        return b;
    }
    while(r>0){
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
 
 
ll lcms(ll a,ll b){
    ll mmr=gcds(a,b);
    a=a/mmr;
    b=b/mmr;
    return a*b*mmr;
}
*/
int main(){
    ll N,K;
    cin>>N>>K;
    ll tmp = N%K;
    ll Tmp = K-tmp;
    if(tmp<Tmp){
        cout<<tmp<<endl;
    }
    else{
        cout<<Tmp<<endl;
    }
}

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

ll mod = 998244353;
//---------------------------------------------------------------------------------------------------
ll f[201010];
void init() {
    f[0] = 1;
    for(int i = 1; i < 201010; i++) f[i] = (f[i - 1] * i) % mod;
}
//---------------------------------------------------------------------------------------------------
ll inv(ll x) {
    ll res = 1;
    ll k = mod - 2;
    ll y = x;
    while (k) {
        if (k & 1) res = (res * y) % mod;
        y = (y * y) % mod;
        k /= 2;
    }
    return res;
}
//---------------------------------------------------------------------------------------------------
ll C(int n, int k) {
    ll a = f[n]; // = n!
    ll b = f[n-k]; // = (n-k)!
    ll c = f[k]; // = k!

    ll bc = (b * c) % mod;

    return (a * inv(bc)) % mod;
}

int power(int a, int n){ 
  if( n == 0 ){ return 1LL;}
  else if( n == 1 ){ return a;}
  else{ 
    if( n % 2 == 0 ){ return (power(a,n/2)*power(a,n/2))%mod;}
    else{ 
      return (((power(a,(n-1)/2)*power(a,(n-1)/2))%mod) * a ) % mod;}
  }
  
}

signed main(void){ 
  
  int n,m,k; cin >> n >> m >> k;
  
  init();
  
  int ans = 0;
  
  for(int p = n-k; p <= n; p++){ 

    int res = C(n-1,p-1);
    
    res = (res*m)%mod;
    
    res = (res*power(m-1,p-1))%mod;
    
    ans = (ans+res)%mod;
  }

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

Measured memory_bytes: 5156
#include <iostream>
#include <iterator>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <numeric>
#include <iomanip>
#include <limits>
#include <set>
#include <map>
#include <type_traits>
#include <cstdint>
 
typedef long long ll;
 
using namespace std;

ll N;
ll A[100010],B[100010],C[100010];
bool AisOK(ll index, ll key)
{ 
  	if(A[index] < key) return true;
    else return false;
}
bool CisOK(ll index, ll key)
{ 
  	if(C[index] > key) return true;
    else return false;
}
ll binary_search(ll key)
{
  ll Al = -1;
  ll Ar = N;
  
  while(Ar > Al+1)
  {
    ll mid = Al +(Ar - Al)/2;  
    if(AisOK(mid,key)) Al = mid;
    else Ar = mid;
  }
  
  ll Cl = -1;
  ll Cr = N;
  
  while(Cr > Cl+1)
  {
    ll mid = Cl +(Cr - Cl)/2;
    if(CisOK(mid,key)) Cr = mid;
    else Cl = mid;
  }
  
  return Ar*(N-Cl-1);
}
int main()
{
  cin >> N;
  for(ll i=0;i<N;i++)cin >> A[i];
  for(ll i=0;i<N;i++)cin >> B[i];
  for(ll i=0;i<N;i++)cin >> C[i];
  sort(A,A+N);
  sort(B,B+N);
  sort(C,C+N);
  
  ll ans = 0;
  for(ll i=0;i<N;i++)
    ans+=binary_search(B[i]);
  
  cout << ans << endl;  
  
  return 0;
}

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

int main(){
    string s,t;
    cin>>s>>t;

    string ans="UNRESTORABLE";
    for(int i=0;i<=(int)(s.size()-t.size());i++){
        bool flag=true;
        string S=s;
        for(int j=0;j<(int)t.size();j++){
            if(s[i+j]!='?'&&s[i+j]!=t[j]) flag=false;
            S[i+j]=t[j];
        }
        if(flag){
            replace(S.begin(),S.end(),'?','a');
            ans=S;
        }
    }
    cout<<ans<<endl;
}

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

using namespace std;

int main(){
	int q;
	double x1,x2,x3,x4,y1,y2,y3,y4,slope1,slope2,naiseki;

	scanf("%d",&q);
	for(int i=0;i<q;i++){
		scanf("%lf %lf %lf %lf %lf %lf %lf %lf",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);
		if(x1 == x2 && x3 == x4){
			printf("2\n");
		}else if(x1 == x2 && x3 != x4){
			if(y3 == y4)printf("1\n");
			else{
				printf("0\n");
			}
		}else if(x1 != x2 && x3 == x4){
			if(y1 == y2)printf("1\n");
			else{
				printf("0\n");
			}
		}else{
			slope1 = (y2-y1)/(x2-x1);
			slope2 = (y4-y3)/(x4-x3);
			naiseki = (x2-x1)*(x4-x3)+(y2-y1)*(y4-y3);
			if(fabs(slope1-slope2) < 0.00000001){
				printf("2\n");
			}else if(fabs(naiseki) < 0.00000001){
				printf("1\n");
			}else{
				printf("0\n");
			}
		}
	}

	return 0;
}



Measured memory_bytes: 2728
#include<iostream>
#include <string>
using namespace std;
int main(){
  int s,ans; cin >> s; string b; cin >> b; char st;
  ans = 1; st = b[0];
  for (int i = 1; i < s; i++){
    if (st!=b[i]) { ans += 1; st = b[i]; } }
  cout << ans << "\n";
  return 0;
}

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

int main(){
	int n, m;
	while( cin >> n, n ){
		int doll[1001][1001] = {0};
		int dp[1001][1001] = {0};
		
		for(int i=0 ; i < n ; i++ ){
			int w, h;
			cin >> w >> h;
			doll[h][w] = 1;
		}
		cin >> m;
		for(int i=0 ; i < m ; i++ ){
			int w, h;
			cin >> w >> h;
			doll[h][w] = 1;
		}
		int ans = 0;
		for(int y=1 ; y < 1001 ; y++ ){
			for(int x=1 ; x < 1001 ; x++ ){
				if( doll[y-1][x-1] == 1 ){
					dp[y][x] = max( dp[y-1][x-1]+1 , max(dp[y-1][x],dp[y][x-1]) );
					ans = max( ans , dp[y][x] );
				}else{
					dp[y][x] = max(dp[y-1][x],dp[y][x-1]);
					ans = max( ans , dp[y][x] );
				}
			}
		}
		cout << ans << endl;
	}
}

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

int main() {
    int n;
    scanf("%d", &n);
    vector<int> p(n);
    rep(i, n) {
        scanf("%d", &p[i]);
    }
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (p[i] != i + 1) {
            cnt++;
            if (cnt > 2) {
                break;
            }
        }
    }
    if (cnt <= 2) {
        printf("YES");
    } else {
        printf("NO");
    }
    return 0;
}

Measured memory_bytes: 256
#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream> 
#include <cmath>
#include <map>
#include <queue>
 
using namespace std;
typedef long long ll;
typedef long double ld;
 
const ll MOD=ll(1e9+7);
 
//repetition
#define REP(i,n)  for(ll i=0;i<n;i++)
 
ll P_POW(ll i, ll n) {
  if(n==0) return 1;
 
  n--;
  ll rep = i;
 
  while(n) {
    rep = rep * i;
    n--;
  }
  return rep;
} 
 
unsigned GetDigit(unsigned num){
    unsigned digit=0;
    while(num!=0){
        num /= 10;
        digit++;
    }
    return digit;
}
 
unsigned binarySearch(ll target, ll max, ll min) {
  while((max - min) > 1) {
      if((max + min)/2 > target) {
        max = (max + min)/2;
        min = min;
      } else {
        max = max;
        min = (max + min)/2;
      }
    }
}
 
ll n;
 
 
long long solve2(long long N) {
    if (N % 2 == 1) return 0;
 
    long long res = 0;
    N /= 2;
    while (N) {
        res += N / 5;
        cout << "N/5: " << N/5 <<  endl;
        cout << "res1: " << res <<  endl;
        N /= 5;
    }
    return res;
}
 
 
ll solve(ll n) {
    if (n % 2 == 1) return 0;
 
    ll res = 0;
    n /= 2;
    int c = 1;
 
    while ((ll) n/((ll)pow(5,c))) {
      res += n/P_POW(5,c);
      c++;
    }
    return res;
}
 
void f(int rest, string s) {
  char abc[] = "abc";
  if(rest == 0) {
    cout << s << endl;
  } else {
    for(int i=0; i < 3; i++) {
      f(rest - 1, s+abc[i]);
    }
  }
} 
 
int main() {
  ll a, n;
  cin >> n;
  // 2次元vector
  // vector<vector<ll>> a(n ,vector<ll>{2,0});
  // vector
  // vector<ll> s(n,0);
  // vector<vector<ll>> v;
  // map<ll,ll> m;
  // priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
 
  vector<ll> ev;
  vector<ll> ov;
 
  map<ll, ll> em;
  map<ll, ll> om;
 
  vector<pair<ll, ll>> epv(n, {0, 0});
  vector<pair<ll, ll>> opv(n, {0, 0});
 
  REP(i, n) {
    cin >> a;
    if(i%2 == 0) {
      ev.push_back(a);
    } else {
      ov.push_back(a);
    }
  }
  
  REP(i, ev.size()) {
    em[ev[i]]++;
  }
 
  REP(i, ov.size()) {
    om[ov[i]]++;
  }

  /*
  cout << "em[0]" << em[0] << endl;
  cout << "em[1]" << em[1] << endl;
  cout << "om[0]" << om[0] << endl;
  cout << "om[1]" << om[1] << endl;
  */

  for(auto&& m: em) {
    epv.push_back({ m.second, m.first });
  }

  for(auto&& m: om) {
    opv.push_back({ m.second, m.first });
  }

  sort(epv.rbegin(), epv.rend());
  sort(opv.rbegin(), opv.rend());

  if(epv[0].second == opv[0].second) {
    cout << n - max((epv[0].first + opv[1].first), (epv[1].first + opv[0].first)) << endl;
  } else {
    cout << n - (epv[0].first+opv[0].first) << endl;
  }
 
}



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

using namespace std;

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

    vector<long long> w(N+1), v(N+1);
    for (int i = 1; i <= N; i++) {
        cin >> w[i] >> v[i];
    }

    // 1からiまでの品物の中で価値の和がj以上の品物の重さの総和の最小値dp[i][j]
    vector<vector<long long>> dp(N+1, vector<long long>(100001, 2000000000));

    // 初期条件
    dp[0][0] = 0;

    // dp開始
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= 100001; j++) {
            // 品物が入る場合、入れる場合と入れない場合を比べて価値が大きい方を取る
            if (j - v[i] >= 0) {
                dp[i][j] = min(dp[i-1][j], dp[i-1][j - v[i]] + w[i]);
            // 品物が入らない場合
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }

    long long answer = 0;

    for (int j = 100000; j >= 1; j--) {
        if (dp[N][j] <= W) {
            answer = j;
            break;
        }
    }

    cout << answer << endl;
	return 0;
}

Measured memory_bytes: 83164
#include <iostream>
#include <fstream>
#include <utility>
#include <vector>
#include <algorithm>

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define chmin(x, y) x = min(x, y)

using namespace std;

typedef long long ll;

const int INF = 1001001001;

int main()
{
    ll n;
    cin >> n;
    vector<ll> a(n);
    REP(i, n)
    {
        int x;
        cin >> x;
        a[x - 1]++;
    }

    sort(a.begin(), a.end());
    vector<int> s(n + 1);
    REP(i, n)
    s[i + 1] = s[i] + a[i];

    for (int k = 1; k <= n; ++k)
    {
        int l = 0;
        int r = n / k + 1;
        while (l + 1 < r)
        {
            int c = (l + r) / 2;
            bool ok = [&](int c) {
                int i = lower_bound(a.begin(), a.end(), c) - a.begin();
                int sum = c * (n - i) + s[i];
                return (sum >= c * k);
            }(c);
            if (ok)
                l = c;
            else
                r = c;
        }
        printf("%d\n", l);
    }

    return 0;
}

Measured memory_bytes: 4352
#include <stdio.h>

int main() {
    long S;
    int h, m, s;

    scanf("%ld", &S);
    s = S % 60;
    S /= 60;
    m = S % 60;
    h = S / 60;

    printf("%d:%d:%d\n", h, m, s);

    return 0;
}

Measured memory_bytes: 592
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vll vector<ll>
typedef long long int ll;
typedef long double ld;
using namespace std;

struct UF{
  std::vector<int> par, dep, sz;
  UF(int n){
    par.resize(n+1), dep.resize(n+1), sz.resize(n+1);
    init(n);
  }
  void init(int nu) {
    for(int iu=0;iu<=nu;iu++){
      par[iu] = iu;
      dep[iu] = 0;
      sz[iu] = 1;
    }
  }
  int find(int xu){
    if(par[xu] == xu) return xu;
    return par[xu] = find(par[xu]);
  }
  void unite(int xu, int yu){
    xu=find(xu);
    yu=find(yu);
    if(xu == yu) return;
    if(dep[xu] < dep[yu]){
      sz[yu] += sz[xu];
      par[xu] = yu;
    }else{
      par[yu] = xu;
      sz[xu] += sz[yu];
      if(dep[xu] == dep[yu]) dep[xu]++;
    }
  }
  bool same(int xu, int yu){
    return find(xu) == find(yu);
  }
};
int main(int argc, char const *argv[]) {
  ll x, y, n, k, l;std::cin >> n >> k >> l;
  UF road(n), train(n);
  for(int i=0;i<k;i++){
    std::cin >> x >> y;
    road.unite(x, y);
  }
  for(int i=0;i<l;i++){
    std::cin >> x >> y;
    train.unite(x, y);
  }
  vvl s = vv(0, 2, 0, ll);
  for(int i=1;i<=n;i++) s.push_back(vll{road.find(i), train.find(i)});
  sort(s.begin(), s.end());
  for(int i=1;i<=n;i++){
    ll t = lower_bound(s.begin(), s.end(), vll{road.find(i), train.find(i)+1}) - s.begin();
    ll k = lower_bound(s.begin(), s.end(), vll{road.find(i), train.find(i)}) - s.begin();
    std::cout << t - k << (i==n?"\n":" ");
  }

  return 0;
}


Measured memory_bytes: 17072
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>

using namespace std;

typedef pair<int, int> P;
typedef pair<int, P> P_;

struct edge{
    P to;
    int cost;
};

map<P, vector<edge>> G;
map<P, int> d;

void dijkstra(P s){
    priority_queue<P_, vector<P_>, greater<P_>> que;
    d[s] = 0;
    que.push(P_(0, s));
    while(!que.empty()){
        P_ p = que.top();que.pop();
        P v = p.second;
        //cout << v.first << ' ' << v.second << endl;
        if(d[v] < p.first) continue;
        for(int i = 0; i < G[v].size(); i++){
            edge e = G[v][i];
            if(d.count(e.to) == 0 || d[v] + e.cost < d[e.to]){
                d[e.to] = d[v] + e.cost;
                que.push(P_(d[e.to], e.to));
            }
        }
    }
}

int main(){
    int N, M;
    cin >> N >> M;
    for(int i = 0; i < M; i++){
        int p, q, c;
        cin >> p >> q >> c;
        p--;
        q--;
        if(G.count(P(p, c)) == 0){
            G[P(p, c)] = {(edge){P(p, 0), 1}};
            G[P(p, c)].push_back((edge){P(q, c), 0});
        }else{
            G[P(p, c)].push_back((edge){P(p, 0), 1});
            G[P(p, c)].push_back((edge){P(q, c), 0});
        }
        if(G.count(P(p, 0)) == 0){
            G[P(p, 0)] = {(edge){P(p, c), 0}};
        }else{
            G[P(p, 0)].push_back((edge){P(p, c), 0});
        }
        if(G.count(P(q, c)) == 0){
            G[P(q, c)] = {(edge){P(q, 0), 1}};
            G[P(q, c)].push_back((edge){P(p, c), 0});
        }else{
            G[P(q, c)].push_back((edge){P(q, 0), 1});
            G[P(q, c)].push_back((edge){P(p, c), 0});
        }
        if(G.count(P(q, 0)) == 0){
            G[P(q, 0)] = {(edge){P(q, c), 0}};
        }else{
            G[P(q, 0)].push_back((edge){P(q, c), 0});
        }
    }
    dijkstra(P(0, 0));
    //cout << d[P(0, 0)] << endl;
    if(d.count(P(N-1, 0)) == 0){
        cout << -1 << endl;
    }else{
        cout << d[P(N-1, 0)] << endl;
    }
}



Measured memory_bytes: 91064
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n-1; i >= 0; i--)
#define all(x) x.begin(), x.end()
using ll = long long;
using pii = pair<int, int>;
const int mod = 1e9+7;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) {
        cin >> a[i];
    }
    map<int, ll> m;
    ll cnt = 0;
    rep(i, n) {
        m[i+a[i]]++;
        if (i > 0) {
            cnt += m[i-a[i]];
        }
    }
    cout << cnt << endl;
}

Measured memory_bytes: 26732
N,W=map(int, raw_input().split())
A=[ map(int, raw_input().split())  for i in range(N) ] 

V=10**5
dp= [ None for i in range(V+1) ]
dp[0]=0


for w,v in A:
	for i in range(V,-1,-1):
		if dp[i] is not None:
			if  0<=i+v<=V:
				if dp[i+v] is None:
					dp[i+v]=dp[i]+w
				else:
					dp[i+v]=min( dp[i+v], dp[i]+w )


for i in range(V,-1,-1):
	if dp[i] is not None:
		if dp[i]<=W:
			print i
			quit()


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

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

	int tp = 0, hp = 0;
	for( int i = 0; i < n; i++ ) {
		string tc, hc;
		cin >> tc >> hc;
		if( tc == hc ) {
			tp += 1;
			hp += 1;
		}
		if( tc > hc ) {
			tp += 3;
		}
		if( tc < hc ) {
			hp += 3;
		}
	}
	cout << tp << " " << hp << endl;
	return 0;
}

Measured memory_bytes: 3172
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ls rt << 1
#define rs rt << 1 | 1
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define X first
#define Y second
#define pcc pair<char, char>
#define rep(i, x, y) for(int (i) = (x); (i) <= (y); (i) ++)
#define eps 1e-9
using namespace std;
const int N = 110;
inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
int n,m;
int main()
{
	ll y = 0, x = 1;
	int n,p;
	n = read();
	p = read();
	rep(i, 1, n)
	{
		int a;
		a = read();
		if(a&1)
		{
			ll t = x;
			x += y;
			y += t;
		}
		else x *= 2, y *= 2;
	}
	if(p == 0) printf("%lld\n", x);
	else printf("%lld\n", y);
	return 0;
}


Measured memory_bytes: 256
/*  -*- coding: utf-8 -*-
 *
 * c.cc: C: Sequence Growing Easy
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 200000;

/* typedef */

typedef long long ll;
typedef vector<int> vi;
typedef queue<int> qi;
typedef pair<int,int> pii;

/* global variables */

int as[MAX_N];

/* subroutines */

/* main */

int main() {
  int n;
  scanf("%d", &n);

  for (int i = 0; i < n; i++) scanf("%d", &as[i]);

  ll cnt = 0;
  int pa = 0;

  for (int i = n - 1; i >= 0; i--) {
    if (as[i] < pa || as[i] > i) {
      puts("-1");
      return 0;
    }

    if (as[i] > pa) cnt += as[i];
    pa = (as[i] > 0) ? as[i] - 1 : 0;
  }

  printf("%lld\n", cnt);
  return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
long long m,n;
int main(){
     cin>>m;
     int k=0;
     while(m){
     	k++;
     	m/=2;
	 }
	 n=1;
	 for(int i=1;i<=k;i++)
	 n*=2;
	 n--;
	 cout<<n;
}

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

using namespace std;

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

	int N,T;
	double A,t;
	vector <double> h;

	cin >> N;
	cin >> T >> A;

	for(int i=0;i<N;i++)
	{
		cin >> t;
		h.push_back(t);
	}

	int idx = 0;
	double num = 100000000;

	for(int i=0;i<N;i++)
	{
		double x = T - (h[i]*0.006);
		//cout << A << ' ' << x << '\n';
		if(abs(A-x)<num)
		{
			num = abs(A-x);
			idx = i+1;
		}
	}

	cout << idx << '\n';
	return 0;
}

Measured memory_bytes: 256
import numpy as np

s=input()
x,y = [int(i) for i in input().split()]

#print(s)

susumu = [0]
for moji in s:
    if moji == 'F':
        susumu[-1] += 1
    else:
        susumu.append(0)

#print(susumu)

syokiti = susumu[0]

susumu_NS = [i for i in susumu[1::2] if i!=0]
susumu_EW = [i for i in susumu[2::2] if i!=0]

x -= syokiti

#print(susumu)
#print(susumu_NS)
#print(susumu_EW)
# ＥＷの部分和でx? NSの部分和でy？

LL = len(s)+2
dp = np.zeros(LL*2, dtype=bool)
dp[LL] = 1
for j in range(len(susumu_NS)):
    dpleft =np.r_[dp[susumu_NS[j]:],np.zeros(susumu_NS[j], dtype=bool)]
    dpright=np.r_[np.zeros(susumu_NS[j], dtype=bool),dp[:-susumu_NS[j]]]
    dp = dpleft|dpright
#    print(dp)

can_y = 0
if dp[y+LL] != False:
    can_y = 1
#print(dp)
#print(susumu_NS)

#########################################
LL = len(s)+2
dp = np.zeros(LL*2, dtype=bool)
dp[LL] = 1
for j in range(len(susumu_EW)):
    dpleft =np.r_[dp[susumu_EW[j]:],np.zeros(susumu_EW[j], dtype=bool)]
    dpright=np.r_[np.zeros(susumu_EW[j], dtype=bool),dp[:-susumu_EW[j]]]
    dp = dpleft|dpright
#    print(dp)

can_x = 0
if dp[x+LL] != False:
    can_x = 1

#print(dp)
#print(susumu_EW)

if can_x == 1 & can_y == 1:
    print('Yes')
else:
    print('No')








Measured memory_bytes: 21308
#include <stdio.h>
#include <algorithm>

int main(){
	long long int n = 0;
	scanf("%lld",&n);
	long long int temp = 0;
	while(n!=0){
		if(n>=25){
			temp += (n/25);
			n = n % 25;
			continue;
		}else if(n<25 && n>=10){
			temp += (n/10);
			n = n % 10;
		}else if(n<10 && n>=5){
			temp += (n/5);
			n = n % 5;
		}else if(n<5){
			temp += (n/1);
			n = n % 1;
		}
	}
	printf("%lld\n",temp);
	
	return 0;
}


Measured memory_bytes: 2764
from collections import deque
n, k = map(int, input().split())
a = list(map(int, input().split()))
#kを法とする配列を作る
a = [(i - 1) for i in a]
acc_a = [0 for i in range(n+1)]
acc_a[0] = 0
acc_a[1] = a[0] % k
#kを法とする累積和
for i in range(2,len(a) + 1):
    acc_a[i] = (a[i - 1] + acc_a[i-1]) % k
ans = 0
count = {}
q = deque()
for i in acc_a:
    if i not in count:
        count[i] = 0
    ans += count[i]
    count[i] += 1
    q.append(i)
    if len(q) == k:
        count[q.popleft()] -= 1
print(ans)

Measured memory_bytes: 113692
import sys
import heapq
input = sys.stdin.readline

n,m = map(int, input().split(' '))
a_list = [-1 * int(i) for i in input().split() ]
heapq.heapify(a_list)
 
for _ in range(m):
    p = heapq.heappop(a_list)
    q = (-1*p //2) * (-1)
    heapq.heappush(a_list, q)    
    
print(-sum(a_list))

Measured memory_bytes: 14168
mod = 10 ** 9 + 7
x, y = map(int,  input().split())

def nCm_mod(A, B, mod):
    mul_one = 1
    mul_two = 1

    for i in range(B):
        mul_one *= A - i
        mul_two *= i + 1
        mul_one %= mod
        mul_two %= mod
    
    return (mul_one * pow(mul_two, mod-2, mod)) % mod

n = (2 * y - x) // 3
m = (2 * x - y) // 3

if (x + y) % 3 != 0 or n < 0 or m < 0:
    print(0)
else:
    comb_num = nCm_mod(n+m, min(n,m), mod)
    print(comb_num)
    

Measured memory_bytes: 3064