akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n-1); i >= 0; i--)
#define all(v) (v).begin(),(v).end()
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 T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template <class T> T lcm(T a, T b) { return a/gcd(a,b)*b; }
typedef pair<int, int> P;
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;
const ll MOD = 1e9+7;

const int MAX_N = 2005;
int n;
vector<pair<ll, int>> A(MAX_N);
vector<vector<ll>> dp(MAX_N, vector<ll>(MAX_N));

// void dfs(int x, int l) {
//     if (x==n) return;
//     dp[x+1][l+1] = max(dp[x+1][l+1], dp[x][l] + A[x].first * abs(A[x].second - l));
//     dfs(x+1, l+1);
//     dp[x+1][l]   = max(dp[x+1][l], dp[x][l] + A[x].first * abs(A[x].second - (n-1-(x-l))));
//     dfs(x+1, l);
// }

int main() {
	cin >> n;
    rep(i,n) {
        ll a;
        cin >> a;
        A[i] = make_pair(a, i);
    }
    sort(A.begin(),A.end());
    reverse(A.begin(),A.end());

    // dfs(0, 0);
    rep(x,n) rep(l,x+1) {
        dp[x+1][l+1] = max(dp[x+1][l+1], dp[x][l] + A[x].first * abs(A[x].second - l));
        dp[x+1][l]   = max(dp[x+1][l], dp[x][l] + A[x].first * abs(A[x].second - (n-1-(x-l))));
    }
    ll ans = 0;
    // rep(i,n) {
    //     cout << dp[1][i] << endl;
    // }
    rep(i,n) {
        ans = max(ans, dp[n][i]);
        // cout << dp[n][i] << endl;
    }
	cout << ans << "\n";
	return 0;
}


Measured memory_bytes: 34480
#define _USE_MATH_DEFINES
#include<iostream>
#include<fstream>
#include<string>
#include<vector>
#include<utility>
#include<algorithm>
#include<climits>
#include<set>
#include<map>
#include<cmath>
#include<iomanip>
#include<iterator>
#include<queue>
#include<stack>
#include<cctype>
#include<deque>
#include<time.h>
#include<bitset>
#include<random>
#include<unordered_set>
#include<unordered_map>
#include<sstream>
#include<random>

//by Skeef79

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

#pragma warning(disable : 4996)
#pragma comment(linker, "/STACK:16777216")
#define pb push_back
#define en '\n'
#define for0(i,n) for(int i = 0;i<n;i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define vec vector
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

const int INF = 2000000000;
const ll LINF = 2000000000000000000;

template<typename T> void print(vector<T>& a)
{
	for (int i = 0; i < a.size(); i++)
		cout << a[i] << ' ';
	cout << en;
}

template<typename T> void print(deque<T>& a)
{
	for (int i = 0; i < a.size(); i++)
		cout << a[i] << ' ';
	cout << en;
}

template<typename T> void print(vector<vector<T>>& a)
{
	for (int i = 0; i < a.size(); i++)
	{
		for (int j = 0; j < a[i].size(); j++)
			cout << a[i][j] << ' ';
		cout << en;
	}
}

template <typename T> void input(vector<T>& a)
{
	for (int i = 0; i < a.size(); i++)
		cin >> a[i];
}

template<typename T> void input(deque<T>& a)
{
	for (int i = 0; i < a.size(); i++)
		cin >> a[i];
}

template<typename T> void input(vector<vector<T>>& a)
{
	for (int i = 0; i < a.size(); i++)
		for (int j = 0; j < a[i].size(); j++)
			cin >> a[i][j];
}

vector<vector<char>> a;
vector<int> di = { 0,-1,0,1 };
vector<int> dj = { -1,0,1,0 };

int n, m;

int path(int sti,int stj ,int fni,int fnj)
{
	if (sti == fni && stj == fnj)
		return 0;

	vector<vector<bool>> used(n, vector<bool>(m,false));

	vector<vector<int>> d(n, vector<int>(m, INF));
	d[sti][stj] = 0;
	queue<pair<int, int>> q;
	q.push({ sti,stj });

	while (!q.empty())
	{
		int i = q.front().first;
		int j = q.front().second;
		q.pop();
		for (int k = 0; k < 4; k++)
		{
			if (i+di[k]>=0 && i+di[k]<n && j+dj[k]>=0 && j+dj[k]<m && !used[i+di[k]][j+dj[k]] && a[i+di[k]][j+dj[k]]=='.')
			{
				used[i + di[k]][j + dj[k]] = true;
				d[i + di[k]][j + dj[k]] = d[i][j] + 1;
				q.push({ i + di[k],j + dj[k] });
			}
		}
	}
	return d[fni][fnj];

}
void solve()
{

	cin >> n >> m;
	a = vector<vector<char>>(n, vector<char>(m));
	input(a);

	int ans = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			for (int k = 0; k < n; k++)
				for (int c = 0; c < m; c++)
					if (a[i][j]!='#' && a[k][c]!='#')
						ans = max(ans, path(i, j, k, c));

	cout << ans;

}

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

#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
#endif

	int tst = 1;
	//cin >> tst;
	while (tst--)
		solve();
}

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

typedef pair<int,int> P;

int n;
int t[10][10],pass[10][10];
int dx[] = {-1,1,0,0};
int dy[] = {0,0,1,-1};
vector<P> v;

bool solve(int x,int y,int rem,int sum,int vi){
	if(sum == 0){
		if(rem == 0){
			if(v.size() - 1 == vi){
				return true;
			}
			return false;
		}
		else if(vi < v.size()-1){
			int nvi = vi + 1;

			pass[y][x] = vi+1;
			if(solve(v[nvi].second,v[nvi].first,rem-1,-t[v[nvi].first][v[nvi].second],nvi)) return true;
			pass[y][x] = 0;
		}
	}
	if(rem <= 0 || sum <= 0 || vi >= v.size()) return false;

	if(t[y][x]>0) pass[y][x] = vi+1;
	for(int i=0;i<4;i++){
		int nx = x + dx[i];
		int ny = y + dy[i];

		if(0<=nx && nx<n && 0<=ny && ny<n && !pass[ny][nx]){
			if(solve(nx,ny,rem-1,sum-t[ny][nx],vi)){
				return true;
			}
		}
	}
	if(t[y][x]>0) pass[y][x] = 0;

	return false;
}

int main(void){
	while(cin>>n,n){
		memset(pass,0,sizeof(pass));
		v.clear();
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				cin>>t[i][j];
				if(t[i][j] < 0){
					v.push_back(P(i,j));
					pass[i][j] = v.size();
				}
			}
		}

		cout<<(solve(v[0].second,v[0].first,n*n-1,-t[v[0].first][v[0].second],0) ? "YES" : "NO")<<endl;
	}

	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using ll = int64_t;
using ld = long double;
using ull = uint64_t;
using namespace std;
using namespace __gnu_pbds;

const int MAXN = 300228;

ll fact[MAXN];
ll rfact[MAXN];

const ll MOD = 998244353;

ll pw(ll a, ll b) {
    if (!b) {
        return 1;
    }

    ll v = pw(a, b / 2);
    v = (v * v) % MOD;

    if (b & 1) {
        v = (v * a) % MOD;
    }

    return v;
}

ll cnk(int n, int b) {
    return fact[n] * rfact[b] % MOD * rfact[n - b] % MOD;
}

int main() {
#ifdef BZ
    freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cout.setf(ios::fixed); cout.precision(20);
    int n, a, b;
    ll k;
    cin >> n >> a >> b >> k;
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) {
        fact[i] = fact[i - 1] * i % MOD;
    }

    rfact[n] = pw(fact[n], MOD - 2);
    for (int i = n; i > 0; --i) {
        rfact[i - 1] = rfact[i] * i % MOD;
    }

    ll ans = 0;

    for (ll acnt = 0; acnt <= n; ++acnt) {
        ll bcnt = (k - (acnt * a)) / b;
        if (bcnt <= n && bcnt >= 0 && (a * acnt + b * bcnt == k)) {
            ans = (ans + cnk(n, acnt) * cnk(n, bcnt)) % MOD;
        }
    }

    cout << ans << "\n";
}

Measured memory_bytes: 4992
#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; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)

int main(){
  string s;
  cin >> s;
  int w;
  cin >> w;
  REP(i, s.length()){
    if(i % w == 0) cout << s[i];
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
using ll=long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MOD  1000000007
const ll INF=1e18;
template<class T>void show(vector<T>v){for (int i = 0; i < v.size(); i++){cerr<<v[i]<<" ";}cerr<<endl;}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b){ a = b; return 1; } return 0; }

const double PI = acos(-1.0);

int main(int argc, char const *argv[]) {
  double a, b, x;
  cin >> a >> b >> x;
  x /= a;
  cout << fixed << setprecision(10);
  if (x > a*b/2) cout << atan2((a*b-x)*2, a*a) * 180 / PI << endl;
  else cout << atan2(b*b, x*2) * 180 / PI << endl;
  return 0;
}

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

int main()
{
  int x, a, b, temp1, temp2;

  cin >> x >> a >> b;

  temp1 = a - x;
  if (0 > temp1) {
    temp1 *= -1;
  }
  temp2 = b - x;
  if (0 > temp2) {
    temp2 *= -1;
  }

  if (temp1 < temp2) {
    cout << "A" << endl;
  } else {
    cout << "B" << endl;
  }
}


Measured memory_bytes: 256
n, m = map(int, input().split())
ps = [input().split() for _ in range(m)]

p_ac = dict()
ac = 0
wa = 0
for i in range(m):
    p, s = ps[i]
    if p not in p_ac and s == 'AC':
        p_ac[p] = i
        ac += 1

for i in range(m):
    p, s = ps[i]
    if p in p_ac.keys() and s == 'WA':
        if i < p_ac[p]:
            wa += 1
print(ac, wa)

Measured memory_bytes: 48680
S = input()
Flag = True
for i, ss in enumerate(S):
    if i % 2 == 0 and ss not in ['R', 'U', 'D']:
        Flag = False
        break
    if i % 2 != 0 and ss not in ['L', 'U', 'D']:
        Flag = False
        break

if Flag:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 38384
import sys
sys.setrecursionlimit(500000)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]


def main():
    N, M = mi()
    A = [input() for i in range(N)]
    B = [input() for i in range(M)]

    for x in range(N-M+1):
        for y in range(N-M+1):
            bl = True
            for i in range(M):
                for j in range(M):
                    if A[x+i][y+j] != B[i][j]:
                        bl = False
            if bl:
                print('Yes')
                return
    print('No')

if __name__ == '__main__':
    main()


Measured memory_bytes: 67832
#include<bits/stdc++.h>
#define F first
#define S second
using namespace std;
char c[500010];
int n,num[500010],nnw;
long long ans;
queue<int>q;
bitset<500010>N;
int main()
{
	scanf("%s",c+1);
	n=strlen(c+1);
	c[0]='>';
	c[n+1]='<';
	num[0]=-1;
	num[n+2]=-1;
	N[0]=true;
	N[n+2]=true;
	for(int i=1;i<=n+1;i++)
	{
		if(c[i-1]=='>'&&c[i]=='<')
		{
			q.push(i);
		}
	}
	while(!q.empty())
	{
		nnw=q.front();
		N[nnw]=true;
		q.pop();
		if(nnw!=1)
		{
			if(N[nnw-2]||c[nnw-2]=='>')
			{
				if(!N[nnw-1])q.push(nnw-1);
			}
		}
		if(nnw!=n+1)
		{
			if(N[nnw+2]||c[nnw+1]=='<')
			{
				if(!N[nnw+1])q.push(nnw+1);
			}
		}
		if(c[nnw-1]=='<'&&c[nnw]=='>')
		{
			num[nnw]=max(num[nnw+1],num[nnw-1])+1;
		}
		else if(c[nnw]=='>')
		{
			num[nnw]=num[nnw+1]+1;
		}
		else if(c[nnw-1]=='<')
		{
			num[nnw]=num[nnw-1]+1;
		}
		ans+=num[nnw];
	}
	printf("%lld",ans);
}


Measured memory_bytes: 3328
program sample
    implicit none
  
    integer(8) :: i,j,m,n,a,b,v,w,t
    
  
    read(*,*) a,v
    read(*,*)b,w
    read(*,*)t
    if (abs(b-a)<=t*(v-w))then
     write(*,*)'YES'
    else
        write(*,*)'NO'
    end if
    stop
end program sample
  



Measured memory_bytes: 2860
str = input().split()
n = int(str[0])
m = int(str[1])

str = input().split()
array = [int(i) for i in str]

sum = 0
for i in array:
    sum += i

cnt = 0
for i in range(n):
    if array[i]*4*m >= sum:
        cnt += 1

if cnt >= m:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#!/usr/bin/env python
# -*- coding: utf-8 -*-

N,K = map(int, input().split())

count = 0
for b in range(1, N+1):
  if b-K <= 0: continue
  x = N // b
  count += (b-K) * x

  if N%b > 0 and N%b >= K:
    if K == 0:
      count += N%b
      continue
    count += N%b-K+1

print(count)


Measured memory_bytes: 2940
a,b,c,d,e,f=map(int, input().split())
 
W=[100*a*x + 100*b*y for x in range(0,31) for y in range(0,31) if 0<(100*a*x+100*b*y)<=f]
S=[c*x+d*y for x in range(0,3001) for y in range(0,3001) if 0<(c*x+d*y)<=f]
 
dense = 0
sugar = 0
mass = 100*a
for w in W:
    for s in S:
        if (w+s<=f and s<=(w*e/100) and dense*(s+w)<s):
            dense=s/(s+w)
            sugar=s
            mass=s+w
print(mass,sugar)

Measured memory_bytes: 12452
#include <stdio.h>
int main(void) {
	int i,max=0,s[100],c[100];
	for(i=0;i<100;i++){
		int ret=scanf("%d,%d",&s[i],&c[i]);
		if(ret==EOF) break;
		if(i>max) max=i;
	}
	int sums=0;
	for(i=0;i<=max;i++){
		sums=sums+(s[i]*c[i]);
	}
	printf("%d\n",sums);
	int sumc=0;
	double adc,adca;
	for(i=0;i<=max;i++){
		sumc=sumc+c[i];
	}
	adc=(double)sumc/(max+1);
	adca=adc+0.5;
	printf("%.0f\n",adca);
	return 0;
}


Measured memory_bytes: 2048
N = int(input())
d = [[0] * 10 for _ in range(10)]
ans = 0

for n in range(1, N+1):
    s = str(n)
    a, b = int(s[0]), int(s[-1])
    d[a][b] += 1

for i in range(10):
    for j in range(10):
        ans += d[i][j] * d[j][i]

print(ans)

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

//factorial
int fact(int n) {
	int a = 1;
	for (int i = 1;i <= n;i++) a *= i;
	return a;
}
///////////////////////////////////////////
long long n,k,a,b=1;
int main(){
    
    cin>>n>>k;
    if(n<k){
        cout<<1<<endl;
        return 0;
    }
    while(n>=b){
        b*=k;
        a++;
    }
    cout<<a<<endl;
}



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

using namespace std;


int main() {
    char m[2][3];
    cin>>m[0][0];
    cin>>m[0][1];
    cin>>m[0][2];
    cin>>m[1][0];
    cin>>m[1][1];
    cin>>m[1][2];
    if(m[0][0]==m[1][2] && m[0][1]==m[1][1] && m[0][2]==m[1][0])cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

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

using namespace std;

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

struct UnionFind {
  vector<int> data;
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) {
    return -data[root(x)];
  }
};

int N, M;
int p[100010];

int main() {
    cin >> N >> M;
    rep(i, N) cin >> p[i+1];
    
    UnionFind uf(N+1);
    rep(j, M) {
        int x, y; cin >> x >> y;
        uf.unionSet(x, y);
    }
    
    int ans = 0;
    rep(i, N) if(uf.findSet(i+1, p[i+1])) ans++;
    cout << ans << endl;
}


Measured memory_bytes: 1024
#include <cstdlib>
#include <iostream>


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

  char c;
  std::cin >> c;
  switch (c) {
    case 'a':
    case 'i':
    case 'u':
    case 'e':
    case 'o':
      std::cout << "vowel" << std::endl;
      break;
    default:
      std::cout << "consonant" << std::endl;
  }

  return EXIT_SUCCESS;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e12;

struct S{
    int to, cost;
    // S(int to, int cost): to(to), cost(cost){}
    bool operator>(const S &s) const{
        return cost > s.cost;
    }
};

int n, m, s, t;
int p[100010];
vector<S> G[100010];
int d[100010];

void dijkstra(int s){
    fill(d, d + n, INF);//V, INF
    d[s] = 0;
    priority_queue<P, vector<P>, greater<P> > q;
    q.push(P(d[s], s));
    while(!q.empty()){
        P p = q.top(); q.pop();
        int from = p.second;
        int cost = p.first;
        if(d[from] < cost) continue;
        rep(i, 0, G[from].size()){
            S e = G[from][i];
            int next = e.to;
            int newCost = e.cost + cost;
            if(d[next] > newCost){
                d[next] = newCost;
                q.push(P(newCost, next));
            }
        }
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> s >> t;
    s--; t--;
    rep(i, 0, n){
        cin >> p[i];
    }
    rep(i, 0, m){
        int a, b;
        cin >> a >> b;
        a--; b--;
        G[a].push_back(S{b, p[b]});
    }
    rep(i, 1, n){
        G[i].push_back(S{i - 1, 0});
    }
    dijkstra(s);
    // for(int ii = 0; ii < n; ii++){
    //     if(ii) cout << ' ';
    //     cout << d[ii];
    // }
    // cout << endl;
    cout << d[t] << endl;
}

Measured memory_bytes: 14332
n=int(input())
memo=[0]*47
def fibo(x):
    if x==0 or x==1:
        return 1
    elif memo[x]!=0:
        return memo[x]
    else:
        tmp=fibo(x-1)+fibo(x-2)
        memo[x]=tmp
        return tmp
print(fibo(n))


Measured memory_bytes: 5600
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define REP(i, n) for ( int i = 0; i < (n); i++ )
 
signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);

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

  int now = 0, sum = 0;
  for ( int i = 0; i < 100; i++ ) {
    if ( now <= c && c <= now+a ) {
      for ( int j = 0; j < 60; j++ ) {
	if ( now+j == c ) {
	  cout << sum+j << endl;
	  return 0;
	}
      }
    }
    sum += a+b;
    now += a+b;
    now %= 60;
  }

  cout << -1 << endl;

  return 0;
}



Measured memory_bytes: 3224
#include<stdio.h>

int main(void){
	
	int d1[4],d2[4];
	short flag[4];
	
	int i,j;
	int h,b;
	
	h = 0;
	b = 0;
	
	while(scanf(" %d %d %d %d",&d1[0],&d1[1],&d1[2],&d1[3]) != EOF){
	scanf(" %d %d %d %d",&d2[0],&d2[1],&d2[2],&d2[3]);
	
	for(i = 0;i < 4;i++){
		if(d1[i] == d2[i]){
			flag[i] = 1;
		}
	}
	
	for(i = 0;i < 4;i++){
		if(flag[i]==1){
			continue;
		}
		for(j = 0;j < 4;j++){
			if(d1[i] == d2[j]){
				b++;
			}
		}
	}
	
	for(i = 0;i < 4;i++){
		if(flag[i]==1){
			h++;
		}
	}
	
	printf("%d %d\n",h,b);
	
	for(i=0;i<4;i++){
		flag[i] = 0;
	}
	
	h = 0;
	b = 0;
	
	}
	
	return(0);
	
}

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

#define d(x) cerr << #x ":" << x << endl;
#define dd(x, y) cerr << "(" #x "," #y "):(" << x << "," << y << ")" << endl
#define rep(i, n) for (int i = (int)(0); i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define dump(v)                  \
    cerr << #v ":[ ";            \
    for (auto macro_vi : v) {    \
        cerr << macro_vi << " "; \
    }                            \
    cerr << "]" << endl;
#define ddump(v)                           \
    cerr << #v ":" << endl;                \
    for (auto macro_row : v) {             \
        cerr << "[";                       \
        for (auto macro__vi : macro_row) { \
            cerr << macro__vi << " ";      \
        }                                  \
        cerr << "]" << endl;               \
    }
using lint       = long long;
const int INF    = 1e9;
const lint LINF  = 1e18;
const double EPS = 1e-10;

int main() {
    int N, X, T;
    cin >> N >> X >> T;

    cout << ((N + X - 1) / X) * T << endl;
    return 0;
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sqr(x) ((x) * (x))
#define X first
#define Y second
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR (i, 0, n)
#define TRACE(x) cout << #x << " = " << x << endl
#define _ << " _ " <<
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define MAXK 1010

int n, k;
int b[2 * MAXK][2 * MAXK], w[2 * MAXK][2 * MAXK], pb[2 * MAXK][2 * MAXK], pw[2 * MAXK][2 * MAXK];
int cntb, cntw;

int main()
{
  scanf("%d%d", &n, &k);
  int K = 2 * k;
  for (int i = 0; i < n; i++) {
    int x1, y1; char c1;
    scanf("%d%d %c", &x1, &y1, &c1);
    if (c1 == 'B') {
      b[x1 % K][y1 % K]++;
      cntb++;
    }
    else {
      w[x1 % K][y1 % K]++;
      cntw++;
    }
  }
  pb[0][0] = b[0][0];
  pw[0][0] = w[0][0];
  for (int i = 1; i < K; i++) {
    pb[0][i] = pb[0][i - 1] + b[0][i];
    pw[0][i] = pw[0][i - 1] + w[0][i];
    pb[i][0] = pb[i - 1][0] + b[i][0];
    pw[i][0] = pw[i - 1][0] + w[i][0];
  }
  for (int i = 1; i < K; i++) {
    for (int j = 1; j < K; j++) {
      pb[i][j] = pb[i - 1][j] + pb[i][j - 1] - pb[i - 1][j - 1] + b[i][j];
      pw[i][j] = pw[i - 1][j] + pw[i][j - 1] - pw[i - 1][j - 1] + w[i][j];
    }
  }
  /// WHITE FIX
  int rj = 0;
  for (int u = 1, d = k; d < K; u++, d++)
    for (int l = 1, r = k; r < K; r++, l++) {
      int wonw = pw[d][r] - pw[d][l - 1] - pw[u - 1][r] + pw[u - 1][l - 1] + pw[u - 1][l - 1] + pw[K - 1][l - 1] - pw[d][l - 1] + pw[u - 1][K - 1] - pw[u - 1][r] + pw[K - 1][K - 1] - pw[K - 1][r] - pw[d][K - 1] + pw[d][r];

      int bonw = pb[d][r] - pb[d][l - 1] - pb[u - 1][r] + pb[u - 1][l - 1] + pb[u - 1][l - 1] + pb[K - 1][l - 1] - pb[d][l - 1] + pb[u - 1][K - 1] - pb[u - 1][r] + pb[K - 1][K - 1] - pb[K - 1][r] - pb[d][K - 1] + pb[d][r];

      int bonb = cntb - bonw;
      int wonb = cntw - wonw;

      rj = max(rj, wonw + bonb);
    }
  /// BLACK FIX
  for (int u = 1, d = k; d < K; u++, d++)
    for (int l = 1, r = k; r < K; r++, l++) {
      int wonb = pw[d][r] - pw[d][l - 1] - pw[u - 1][r] + pw[u - 1][l - 1] + pw[u - 1][l - 1] + pw[K - 1][l - 1] - pw[d][l - 1] + pw[u - 1][K - 1] - pw[u - 1][r] + pw[K - 1][K - 1] - pw[K - 1][r] - pw[d][K - 1] + pw[d][r];

      int bonb = pb[d][r] - pb[d][l - 1] - pb[u - 1][r] + pb[u - 1][l - 1] + pb[u - 1][l - 1] + pb[K - 1][l - 1] - pb[d][l - 1] + pb[u - 1][K - 1] - pb[u - 1][r] + pb[K - 1][K - 1] - pb[K - 1][r] - pb[d][K - 1] + pb[d][r];

      int wonw = cntw - wonb;
      int bonw = cntb - bonb;

      rj = max(rj, wonw + bonb);
    }
  cout << rj;
  return 0;
}


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

int main() {

  while( true ) {

    long long int n;
    cin >> n;
    if ( n == 0 ) break;

    vector< string > v;

    long long int m = 0;

    for ( long long int i = 0; i < n; i++ ) {

      string in;
      cin >> in;
      for ( long long int j = 0; j < in.size(); j++ ) {
	if ( in[j] == '.' ) {
	  in[j] = ' ';
	}else {
	  if ( j != 0 ) in[j-1] = '+';
	  break;
	}
      }
      v.push_back( in );
      long long int insize = in.size();
      m = max( m, insize );

    }

    for ( long long int x = 0; x < m; x++ ) {
      bool f = false;
      for ( long long int i = n - 1; i >= 0; i-- ) {
	if ( x < v[i].size() ) {
	  if ( v[i][x] == '+' ) {
	    f = true;
	  }else if ( v[i][x] == ' ' ) {
	    if ( f == true ) {
	      v[i][x] = '|';
	    }
	  }else {
	    f = false;
	  }
	}
      }
    }

    for ( long long int i = 0; i < n; i++ ) {
      cout << v[i] << endl;
    }

  }

  return 0;

}

Measured memory_bytes: 1592
N = int(input())
A = list(map(int, input().split()))
 
B = [0 for i in range(max(A)+1)]
 
for i in range(2, len(B)):
  if B[i] != 0:
    continue
  for j in range(i, len(B), i):
    B[j] = i

def func(X):
  buf = set()
  while X>1:
    x = B[X]
    buf.add(x)
    while X%x==0:
      X = X//x
  #print(buf)
  return buf
 
set1 = func(A[0])
set2 = func(A[0])
totallen = len(set1)
for a in A[1:]:
  set3 = func(a)
  totallen += len(set3)
  #print(a, set1, set2)
  set1 |= set3
  set2 &= set3
  #print(set1, set2, set3)
#print(totallen, set1, set2)
if len(set2)!=0:
  print("not coprime")
elif len(set1)==totallen:
  print("pairwise coprime")
else:
  print("setwise coprime")

Measured memory_bytes: 223964
#define _CRT_SECURE_NO_WARNINGS
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define all(c) begin(c), end(c)
#define range(i,a,b) for(int i = a; i < (int)(b); i++)
#define rep(i,b) range(i,0,b)
#define pb push_back
#define eb emplace_back

using ld = long double;
const ld EPS = 1e-8;
typedef vector<ld> vec;
typedef vector<vec> mat;

mat GaussJordan(mat A){
    int n = A.size();
    int m = A[0].size();
    rep(i,n){
        int pivot = i;
        range(j,i,n) if(abs(A[j][i]) > abs(A[pivot][i])) pivot = j;
        swap(A[i], A[pivot]);
        if(abs(A[i][i]) < EPS) return {};
        range(j,i+1,m) A[i][j] /= A[i][i];
        rep(j,n) if(i != j) range(k,i+1,m) A[j][k] -= A[j][i] * A[i][k];
    }
    mat x(n, vec(m-n));
    rep(i,n) rep(j,m-n) x[i][j] = A[i][n+j];
    return x;
}

int d;
vec b;

auto y = [](const vec &f, ld x){
    ld res = 0, cur = 1;
    rep(i,d+1){
        res += cur * f[i];
        cur *= x;
    }
    return res;
};

int solve(){
    mat A(d+3, vec(d+2));
    rep(i,d+3){
        ld cur = 1;
        rep(j,d+1){
            A[i][j] = cur;
            cur *= i;
        }
        A[i][d+1] = b[i];
    }
    vector<int> cnt(d+3);
    rep(i,d+3)rep(j,i){
        mat P;
        vector<pair<int,ld>> test;
        rep(k,d+3){
            if(k == i || k == j){
                test.eb(k,b[k]);
            } else {
                P.pb(A[k]);
            }
        }
        mat c = GaussJordan(P);
        vec C(c.size());
        rep(i,c.size()) C[i] = c[i][0];
        rep(k,2){
            int x = test[k].first;
            ld resy = y(C, x);
            ld expy = test[k].second;
            cnt[x] += abs(expy - resy) > 1e-3;
        }
    }
    return max_element(all(cnt)) - cnt.begin();
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    while(cin >> d && d){
        b.resize(d+3);
        rep(i,d+3) cin >> b[i];
        cout << solve() << endl;
    }
}

Measured memory_bytes: 3260
layers = [1] * 51
patties = [1] * 51
for i in range(1, 51):
    layers[i] = 3 + layers[i-1] * 2
    patties[i] = 1 + patties[i-1] * 2


def count_patties(l, x):
    if l == 0 and x == 1:
        return 1
    if x <= 1:
        return 0
    y = layers[l-1]
    if x <= y+1:
        return count_patties(l-1, max(x-1, 0))
    else:
        return count_patties(l-1, min(x-y-2, y)) + patties[l-1] + 1


def main():
    N, X = map(int, input().split())
    print(count_patties(N, X))


if __name__ == "__main__":
    main()


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

using namespace std;

int main() {
    int N, K;
    long long int R, S, P;
    string T;
    cin >> N >> K;
    cin >> R >> S >> P;
    cin >> T;
    
    vector<vector<long long int> > memo(4, vector<long long int>(N+1, 0));
    for(int n=1; n<=K; n++) {
        if(T[n-1]=='s') {
            memo[1][n] = R;
        } else if(T[n-1]=='p') {
            memo[2][n] = S;
        } else {
            memo[3][n] = P;
        }
    }
    // for(int i=1; i<=3; i++) {
    //     for(int n=1; n<=N; n++) {
    //         cout << memo[i][n] << " ";
    //     }
    //     cout << endl;
    // }
    for(int n=K+1; n<=N; n++) {
        for(int i=1; i<=3; i++) {
            if(i==1) {
                memo[1][n] = max(memo[2][n-K], memo[3][n-K]);
                if(T[n-1]=='s') memo[1][n]+=R;
            } else if(i==2) {
                memo[2][n] = max(memo[1][n-K], memo[3][n-K]);
                if(T[n-1]=='p') memo[2][n]+=S;
            } else {
                memo[3][n] = max(memo[1][n-K], memo[2][n-K]);
                if(T[n-1]=='r') memo[3][n]+=P;
            }
        }
    }
    
    // for(int i=1; i<=3; i++) {
    //     for(int n=1; n<=N; n++) {
    //         cout << memo[i][n] << " ";
    //     }
    //     cout << endl;
    // }
    
    long long int ans=0;
    for(int n=N-K+1; n<=N; n++) {
        ans += max(max(memo[1][n], memo[2][n]), memo[3][n]);
    }
    cout << ans << endl;


    return 0;
    
}

Measured memory_bytes: 4352
#include<iostream>
#include<cstdio>
#include<string>
#include<typeinfo>

int main(){
    int N, S = 0;
    std::string input;
    std::cin >> input;
    for(int i = 0; i < input.size(); i++){
        S += (int)(input[i] - '0');
    }
    N = std::atoi(input.c_str());
    if(N % S == 0) printf("Yes");
    else printf("No");
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
# define ll long long int
# define inf (1ll<<60)
ll dp[401][401];
ll add[401][401];

ll solve(ll arr[],int s,int e)
{
  if(s==e)
  {
    return 0;
  }
  if(dp[s][e]!=-1)
  {
    return dp[s][e];
  }
  ll min1= inf;
  for(int k=s;k<e;k++)
  {
    min1=min(min1,add[s][e]+solve(arr,s,k)+solve(arr,k+1,e));

  }

return dp[s][e]= min1;

}

void preprocessor(ll arr[],ll n)
{
  for(int i=0;i<n;i++)
  {
    for(int j=i;j<n;j++)
    {
      add[i][j]= arr[j] +((j==i)? 0: add[i][j-1]);
    }
  }
}

int main()
{
  ll n;
  cin>>n;
  ll arr[n];
  memset(dp,-1,sizeof(dp));
  for(ll i=0;i<n;i++)
  {
    cin>>arr[i];
  }
  preprocessor(arr,n);
  cout<<solve(arr,0,n-1)<<endl;

}


Measured memory_bytes: 6152
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Numerics;

namespace Atcoder {
    class Program {
        static void Main(string[] args) {
            //var N = int.Parse(Console.ReadLine());
            //var inputList = new List<int>();
            //foreach (var i in Enumerable.Range(0, N))
            //    inputList.Add(int.Parse(Console.ReadLine()));


            var NK = Console.ReadLine().Split(' ');
            var N = int.Parse(NK.First());
            var K = int.Parse(NK.Last());

            long count = 0;
            for (int b = 1; b <= N; b++) {
                count += (max(b - K, 0) * (N / b) + max((N % b) - K + 1, 0));
                if (K == 0)
                    count -= 1;
            }
            Console.WriteLine(count);
            return;
        }

        static long max(long left, long right) {
            if (left >= right)
                return left;
            return right;
        }
    }
}


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

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

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

  int d = 0;
  for (int i = 0; i < n - 1; i++) {
    for (int j = i + 1; j < n; j++) {
      d = max(d, abs(a[i] - a[j]));
    }
  }

    cout << d << endl;
}

Measured memory_bytes: 256
import math
ni = int(input())
xi = map(int, raw_input().split())
yi = map(int, raw_input().split())

p1 = []
p2 = []
p3 = []
p4 = []
for x, y in zip(xi, yi):
    p1.append(abs(x - y))
    p2.append(abs(x - y)**2)
    p3.append(abs(x - y)**3)
    p4.append(abs(x - y))

print '%.8f' % reduce(lambda x, y: x + y, p1)
print '%.8f' % reduce(lambda x, y: x + y, p2) ** (1.0/2.0)
print '%.8f' % reduce(lambda x, y: x + y, p3) ** (1.0/3.0)
print '%.8f' % max(p4)

Measured memory_bytes: 6740
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <functional>
#include <utility>
using namespace std;

int main(){
  int a, b, c, x;
  cin >> a >> b >> c >> x;
  int cnt = 0;
  for(int i = 0; i <= a; i++){
    for(int j = 0; j <= b; j++){
      for(int k = 0; k <= c; k++){
        if(500 * i + 100 * j + 50 * k == x){cnt++;}
      }
    }
  }
  cout << cnt << endl;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
    int H,W;
    while(true){
        cin>>H>>W;
        if(H==0 && W==0) break;
        else{
            for(int i=0;i<H;i++){
                for(int j=0;j<W;j++){
                    if((i+j)%2==0){
                        cout<<'#';
                    }else{
                        cout<<'.';
                    }
                }cout<<endl;
            }cout<<endl;
        }
    }
    return 0;
}


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

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

  int n;
  cin>>n;
  vector<int> cnt(n,0);
  for(int i=0; i<n-1; ++i){
    int x; cin>>x; x--;
    cnt[x]++;
  }
  for(int i=0; i<n; ++i){
    cout<<cnt[i]<<'\n';
  }

	return 0;
}


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

int main() {
    int a, b;
    while (cin >> a >> b) {
        int c = a + b;
        int ans = 0;
        while (c > 0) {
            c /= 10;
            ++ans;
        }
        cout << ans << endl;
    }
    
    return 0;
}


Measured memory_bytes: 3120
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <utility>
#include <cmath>
#include <climits>

#define ll long long int
#define pb push_back
#define mk make_pair
#define pq priority_queue

using namespace std;
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
const int inf = 1e9;
const ll linf = 1LL << 50;
const double EPS = 1e-10;

int main(int argc, char const* argv[])
{
  int n, a, b;
  cin >> n >> a >> b;
  bool alice = true;
  while(true){
    alice = true;
    if(a == b + 1 || a == b - 1)break;
    if(a > b)a--;
    else a++;
    alice = false;
    if(a == b + 1 || a == b - 1)break;
    if(a > b)b++;
    else b --;
  }
  if(alice)cout << "Borys" << endl;
  else cout << "Alice" << endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
int main()
{
	int g,c1,c5,c10,c50,c100,c500;
	cin>>c1>>c5>>c10>>c50>>c100>>c500;
	g=c1+c5*5+c10*10+c50*50+c100*100+c500*500;
	if(g>=1000)
		cout<<"1"<<endl;
	else
		cout<<"0"<<endl;
	return 0;
}


Measured memory_bytes: 3112
#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#include<complex>
using namespace std;

typedef complex<double> P;

#define X real()
#define Y imag()
typedef int kz;

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

int main(){
    int mod=1000000007;
    int n;
    double a,b,c,d,e,f,g,h;
    while (scanf("%lf %lf %lf %lf %lf %lf %lf %lf",&a,&b,&c,&d,&e,&f,&g,&h)!=EOF) {
        if (g<a || c<e || h<b || d<f) {
            printf("NO\n");
        } else {
            printf("YES\n");
        }
    }
    return 0;
}

Measured memory_bytes: 3224
s = input()
t = input()
s = "".join(sorted(s))
t = "".join(sorted(t, reverse=True))
#print(s)
#print(t)
N = min(len(s), len(t))
f = False
for i in range(N):
  if s[i] < t[i]:
    print('Yes')
    f = True
    break
  elif s[i] > t[i]:
    print('No')
    f = True
    break
if not f:
  if len(s) < len(t):
    print('Yes')
  else:
    print('No')


Measured memory_bytes: 3064
#!/usr/bin/env python3
import sys


def solve(K: int, S: str):
    if len(S) <= K:
        print(S)
    else:
        print(S[:K] + "...")
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(K, S)

if __name__ == '__main__':
    main()

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

int main(){
	int i,j,k,n,m,l,f,x,y,z; string s;
	cin >> x >> y;
	if(y % x == 0) cout << x + y << endl;
	else cout << y -x << endl;
}

Measured memory_bytes: 256
if __name__ == "__main__":
    x = input()
    x = int(x)
    x = x % 10
    if x==2 or x==4 or x==5 or x==7 or x==9:
        y = 'hon'
    elif x==3:
        y = 'bon'
    else:
        y = 'pon'

    print(y)

Measured memory_bytes: 9172
integer d,n,a,b,i,p
read*,d,n
b = 100**d
p = 100**(d+1)
a = 0
i = 0
do while (i < n)
   a = a + b
   if (mod(a,p) == 0) cycle
   i = i + 1
enddo
print'(i0)',a
end

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define SORT(x) sort(x.begin(),x.end(),greater<ll>())
#define ALL(x) x.begin(),x.end()
#define rep(i, n) for(int i = 0; i < n; i++)
#define reps(i, m, n) for(int i = m; i < n; i++)
#define repr(i, m, n) for(int i = m; i >= n; i--)
#define INF 1000000000000000003 //1000000007
#define PI (acos(-1))
#define MOD 1000000007
using namespace std;
typedef long long ll;


void Main(){

  int N;
  cin>>N;
  int a[100001]={};
  rep(i,N){
    int aa;
    cin>>aa;
    ++a[aa];
  }

  int ans=0;
  reps(i,1,100000){
    int buff=a[i-1]+a[i]+a[i+1];
    ans=max(buff,ans);
  }

  cout<< ans<<"\n";
}

//-----------------------------------
int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  Main();
}
//-----------------------------------


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

using namespace std;

using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;

using _loop_int = int;
#define REP(i,n) for(_loop_int i=0; i<(_loop_int)(n); i++)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a); i<(_loop_int)(b); i++)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1; i>=(_loop_int)(a); i--)

#define CHMIN(a,b) (a)=min((a),(b))
#define CHMAX(a,b) (a)=max((a),(b))
#define ALL(v) (v).begin(),(v).end()

#define DEBUG(x) cerr<<#x<<": "<<(x)<<endl
#define DEBUG_VEC(v) cerr<<#v<<": ";REP(__i,(v).size())cerr<<((v)[__i])<<", ";cerr<<endl

const ll MOD = 998244353ll;

int n;
int x[252521], y[252521];
int val[252521][4];
pii ps[252521];

const int N = 252521;
int bit[N+10];
void add(int a, int w){
    a++;
    for(int x=a; x<=N; x+=x&-x)bit[x]+=w;
}
int sum(int a){
    a++;
    int ret = 0;
    for(int x=a; x>0; x-=x&-x)ret+=bit[x];
    return ret;
}

vi xs, ys;

ll modpow(ll a, ll b){
    ll r=1;
    while(b){
        if(b&1)r=r*a%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return r;
}
ll modinv(ll a){
    return modpow(a,MOD-2);
}

int main(){
    scanf("%d",&n);
    REP(i,n)scanf("%d%d",x+i,y+i);
    // zaatu
    {
        set<int> X,Y;
        REP(i,n)X.insert(x[i]),Y.insert(y[i]);
        map<int,int> mx,my;
        int it=0;
        for(int x : X)mx[x]=it++;
        it = 0;
        for(int y : Y)my[y]=it++;
        REP(i,n)x[i]=mx[x[i]],y[i]=my[y[i]];
    }
    REP(i,n)ps[i] = pii(x[i],y[i]);
    sort(ps,ps+n);

    fill(bit,bit+N,0);
    REP(i,n){
        int cnt = sum(ps[i].second);
        val[i][0] = cnt;
        val[i][1] = i-cnt;
        add(ps[i].second,1);
    }
    fill(bit,bit+N,0);
    FORR(i,0,n){
        int cnt = sum(ps[i].second);
        val[i][3] = cnt;
        val[i][2] = (n-1-i)-cnt;
        add(ps[i].second,1);
    }

    ll ans = 0;
    ll mul = modpow(2,n-1);
    REP(i,n){
        ans += mul;
        ans %= MOD;
        REP(msk,1<<4){
            if(__builtin_popcount(msk)>=3){
                ll add = 1;
                REP(j,4)if(msk>>j&1){
                    int c = val[i][j];
                    add *= modpow(2,c)-1;
                    add %= MOD;
                }
                ans += add;
                ans %= MOD;
            }else if(msk==0b0101){
                ll add = 1;
                REP(j,4)if(j==0 || j==2){
                    int c = val[i][j];
                    add *= modpow(2,c)-1;
                    add %= MOD;
                }
                ans += add;
                ans %= MOD;
            }else if(msk==0b1010){
                ll add = 1;
                REP(j,4)if(j==1 || j==3){
                    int c = val[i][j];
                    add *= modpow(2,c)-1;
                    add %= MOD;
                }
                ans += add;
                ans %= MOD;
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 46464
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
 
  if (A + B > C + D) {
    cout << "Left" << endl;
  }
  else if (A + B == C + D) {
    cout << "Balanced" << endl;
  }
  else {
    cout << "Right" << endl;
  }
}

Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using System.Globalization;
using System.Diagnostics;
using System.Threading.Tasks;



class Myon
{
    public Myon() { }
    public static int Main()
    {
        new Myon().calc();
        return 0;
    }
    

    Scanner cin;

    void calc()
    {
        cin = new Scanner();
        int N = cin.nextInt();
        int[] A = cin.ArrayInt(N);
        int ans = 0;
        Array.Sort(A);
        Array.Reverse(A);
        for (int i = 0; i < N; i++)
        {
            if (i % 2 == 0) ans += A[i];
            else ans -= A[i];
        }
        Console.WriteLine(ans);
    }
}




class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0)
    {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0)
    {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }


    public double[] ArrayDouble(int N, double add = 0)
    {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}



Measured memory_bytes: 11220
import java.util.Scanner;
class Main{
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int S =scan.nextInt();
int h=S / 3600;
int m=S % 3600 / 60;
int s=S % 60;
System.out.println(h+ ":" + m + ":" + s);
   }
}



Measured memory_bytes: 26172
from numpy import cumsum
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
sa = cumsum(a)
sb = cumsum(b)
ans = 0
for i in range(n):
    ans = max(ans, sa[i] + sb[n-1] - sb[i] + b[i])

print(ans)


Measured memory_bytes: 27280
#include <cstdio>
#include <algorithm>
#include <cmath>
#define Rint register int
#define LL long long
#define F(x,y,z) for(Rint x=y;x<=z;++x)
#define D(x,y,z) for(Rint x=y;x>=z;--x)
using namespace std;
LL Min(LL x,LL y){return x<y?x:y;}
LL Max(LL x,LL y){return x>y?x:y;}
inline LL R(){
    char c='!';LL x=0,z=1;
    for( ; c>'9'||c<'0';c=getchar()) if(c=='-')z=-1;
    for(;c>='0'&&c<='9';c=getchar()) x=x*10+c-'0';
    return x*z;
}
int n,m,Sum;

int main(){
	n=R();
	m=n;
	while (m) Sum+=m%10,m/=10;
	printf(n%Sum==0?"Yes":"No");
	return 0;
}



Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
using Graph=vector<vector<int>>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
typedef long long ll;
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

int main(){
    string S;
    cin>>S;
    reverse(S.begin(),S.end());
    bool flag=true;
    string S1="maerd";
    string S2="remaerd";
    string S3="esare";
    string S4="resare";
    int i=0;
    while(i<S.size()){
        if(!flag){
            break;
        }
        bool flag2=false;
        if(S.substr(i,5)==S1){
            i=i+5;
            flag2=true;
        }
        else if(S.substr(i,5)==S3){
            i=i+5;
            flag2=true;
        }
        else if(S.substr(i,7)==S2){
            i=i+7;
            flag2=true;
        }
        else if(S.substr(i,6)==S4){
            i=i+6;
            flag2=true;
        }
        if(flag2==false){
            flag=false;
        }
    }
    if(flag){
        cout<<"YES"<<endl;
    }
    else{
        cout<<"NO"<<endl;
    }
}

Measured memory_bytes: 512
h,w,n=map(int,input().split())
sy,sx=map(int,input().split())
s=input()
t=input()
for i in range(n):
  tmp1=s[i]
  tmp2=t[i]
flag=True
for i in range(4):
  if i==0 or i==1:
    pos=sx
  elif i==2 or i==3:
    pos=sy
  exist=False
  for j in range(1,n+1):
    tmp1=s[j-1]
    tmp2=t[j-1]
    if i==0:
      if tmp1=='L':
        pos-=1
        if pos==0:
          flag=False
      if tmp2=='R':
        pos+=1
        if pos>w:
          pos=w
      if tmp1=='R':
        if pos==w and exist==True:
          pos=w-1
      if tmp2=='L':
        exist=True
    elif i==1:
      if tmp1=='R':
        pos+=1
        if pos>w:
          flag=False
      if tmp2=='L':
        pos-=1
        if pos==0:
          pos=1
      if tmp1=='L':
        if pos==1 and exist==True:
          pos=2
      if tmp2=='R':
        exist=True
    elif i==2:
      if tmp1=='U':
        pos-=1
        if pos==0:
          flag=False
      if tmp2=='D':
        pos+=1
        if pos>h:
          pos=h
      if tmp1=='D':
        if pos==h and exist==True:
          pos=h-1
      if tmp2=='U':
        exist=True
    elif i==3:
      if tmp1=='D':
        pos+=1
        if pos>h:
          flag=False
      if tmp2=='U':
        pos-=1
        if pos==0:
          pos=1
      if tmp1=='U':
        if pos==1 and exist==True:
          pos=2
      if tmp2=='D':
        exist=True
if flag==True:
  print('YES')
else:
  print('NO')

Measured memory_bytes: 3904
a = int(input())

from collections import defaultdict
d = defaultdict(int)
d[a] += 1


for i in range(2, 1000001):
    
    if a % 2 == 0:
        a //= 2
    else:
        a = 3*a + 1
        
    if d[a] == 1:
        print(i)
        break
    else:
        d[a] += 1

Measured memory_bytes: 3316
def insertionSort(self,len):
    for i in range(1,len,1):
        print(*self)
        v = self[i] #2
        j = i - 1
        while j >= 0 and self[j] > v:
            self[j+1] = self[j]
            j-=1
            self[j+1] = v
    print(*self)
numslen = int(input())
nums = [int(e) for e in input().split()]
insertionSort(nums,numslen)


Measured memory_bytes: 5976
#include<bits/stdc++.h>
using namespace std;
#define pi 3.1416
long long int x=1,y=1,i,j;
double  t,k,sum,ar[100000],br[10000];
int facto(long long int p)
{if(x>p)
return y;
    y=y*x;
    x++;
    return facto(p);
}
int main()
{cin>>t;
x=facto(t);
for(i=1;i<=t;i++)
{
    cin>>ar[i]>>br[i];
}
for(i=1;i<=t;i++)
{
for(j=1;j<=t;j++)
{
    if(i!=j)
    {
            k=sqrt((ar[i]-ar[j])*(ar[i]-ar[j])+(br[i]-br[j])*(br[i]-br[j]));
            k=k*1.0;
            sum=sum+k;

    }



}
}
printf("%0.10lf\n",(sum/t)*1.0);
}




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

int main() {
    int n, c;
    cin >> n >> c;
    vector<vector<int>> d(c, vector<int>(c));
    vector<vector<int>> a(n, vector<int>(n));
    map<int, int> mp[3];
    for (auto& v1 : d) for (auto& v2 : v1) { cin >> v2; }
    for (auto& v1 : a) for (auto& v2 : v1) { cin >> v2;v2--; }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            mp[(i+j)%3][a[i][j]]++;
        }
    }
    
    long long ans = INT64_MAX;
    for (int c1 = 0; c1 < c; c1++) for (int c2 = 0; c2 < c; c2++) {
        if (c1 == c2) continue;
        for (int c3 = 0; c3 < c; c3++) if (c1 != c3 && c2 != c3) {
            int ch[3] = {c1, c2, c3};
            long long res = 0;
            for (int i = 0; i < 3; i++) {
                for (auto& e : mp[i]) res += (d[e.first][ch[i]] * e.second);
            }
            if (ans > res) ans = res;
        }
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1280