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

int main()
{
    double a;
    cin >> a;
   cout <<fixed << setprecision(6) << a * a * M_PI << " ";
   cout << fixed << setprecision(6) << 2 * a * M_PI << endl; 
    return 0;
}



Measured memory_bytes: 3292
#include <iostream>

using namespace std;
int main()
{
    int k,n;
    cin >> k >> n;
    int arr[n];
    int arr2[n];
    for(int i = 0; i<n; i++){
        cin >> arr[i];
    }
    int maxDis = 0;
    for(int i = 0; i<n-1; i++){

        int d = arr[i+1]-arr[i];
        if(d>=maxDis){
            maxDis = d;
        }
    }
    int d = k-arr[n-1]+arr[0];
    if(d>=maxDis){
        maxDis = d;
    }
    cout << k-maxDis << endl;
}

Measured memory_bytes: 1024
def test():
    n = int(input())
    a = []
    for i in range(n):
        a.append(input().split())
    b = sorted(a,key = lambda x: (x[0],-int(x[1])))
    for i in range(n):
        print(a.index(b[i])+1)


if __name__ == "__main__":
    test()


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(int i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(int i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(int i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define uniq(x) (x).erase(unique((x).begin(), (x).end()), (x).end())

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // std::ifstream in("input.txt");
    // std::cin.rdbuf(in.rdbuf());
    int n;
    cin >> n;
    multiset<int> ms;
    rep(i, n) {
        int a;
        cin >> a;
        auto it = ms.lower_bound(a);
        if (it == ms.begin()) {
            ms.insert(a);
        }
        else {
            ms.erase(--it);
            ms.insert(a);
        }
    }
    cout << sz(ms) << endl;
    return 0;
}


Measured memory_bytes: 4992
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <deque>
#include <numeric>
using lint = long long;

lint n, m, q;

class Kumi
{
public:
    lint a, b, c, d;

    Kumi(lint a, lint b, lint c, lint d) : a(a),
                                           b(b),
                                           c(c),
                                           d(d)
    {
        a = a;
        b = b;
        c = c;
        d = d;
    }

    Kumi(){};
};

lint score(std::vector<lint> a, const std::vector<Kumi> &querys)
{
    lint sum_d = 0;
    for (auto query = querys.begin(); query != querys.end(); query++)
    {
        if (a[query->b - 1] - a[query->a - 1] == query->c)
        {
            sum_d += query->d;
        }
    }

    return sum_d;
}

lint max_a(std::vector<lint> a, const std::vector<Kumi> &querys)
{
    if (a.size() == n)
    {
        return score(a, querys);
    }
    else
    {
        lint max_d = 0;
        lint right = a.back();
        for (lint i = right; i <= m; i++)
        {
            lint cur_d = 0;
            auto next_a = a;
            next_a.push_back(i);
            cur_d = max_a(next_a, querys);

            if (cur_d > max_d)
            {
                max_d = cur_d;
            }
        }
        return max_d;
    }
}

int main()
{
    scanf("%lld", &n);
    scanf("%lld", &m);
    scanf("%lld", &q);

    std::vector<Kumi> querys(q);

    for (int i = 0; i < q; ++i)
    {
        lint a, b, c, d;
        scanf("%lld", &a);
        scanf("%lld", &b);
        scanf("%lld", &c);
        scanf("%lld", &d);

        Kumi add(a, b, c, d);

        querys[i] = add;
    }

    lint ans = max_a(std::vector<lint>{1}, querys);

    printf("%lld", ans);

    return 0;
}


Measured memory_bytes: 3792
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <string.h>
#include <cstdio>
#include <tuple>
#include <numeric>
using namespace std; using ll = long long; using ld = long double;  using pll = pair<ll, ll>;
using vl = vector<ll>; using vll = vector<vl>; using vpll = vector<pll>;
using vs = vector<string>; using tll = tuple<ll, ll, ll>; using vtll = vector<tll>;
const ld PI = 3.1415926535897932;
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define co(i) cout << i << endl;
#define co2(i,j) cout << i << " " << j << endl;
#define co3(i) cout << i << " ";
#define po(i) cout << i.first << " " << i.second << endl;
void in() {}
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail>
void debug_out(Head h, Tail... t) {
	cerr << " " << h;
	if (sizeof...(t) > 0) cerr << " :";
	debug_out(t...);
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> vec) {
	for (size_t i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
	return os;
}
ll ctoi(char c) {
	switch (c) {
	case '0': return 0; case '1': return 1; case '2': return 2;
	case '3': return 3; case '4': return 4; case '5': return 5;
	case '6': return 6; case '7': return 7; case '8': return 8;
	case '9': return 9;  default: return 0;
	}
}
bool pairCompare(const pll firstElof, pll secondElof)
{
	return firstElof.first > secondElof.first;
}
//**Snippetリスト**//
//rep, vin, all, iteLoop, bitSearch, bitList, nod, digitDP, treeDP//
//gcdlcm, isPrime, eratos, primeFactorize, Npow, combination, divisor, modinv, doubling//
//dfs, bfs, dijkstra, WarshallFloyd, BellmanFord, UnionFind, Kruskal, RMQ, LCA//
ll i, j, k, l; ll N, M, K, H, W, L, X, Y, Z, R, Q;
ll MOD = 1000000007, INF = 1LL << 60, ans = 0, z = 0, o = 1;
vl flag, D; vll path; vll A;
//***********//
vl bitList(ll n, ll k, ll f) {
	vl bitList(k);
	for (ll i = 0; i < k; i++) {
		bitList[i] = f % n;
		f /= n;
	}
	return bitList;
}
int main() {
	ll A, B, C;
	cin >> A >> B >> C;
	cin >> K;
	for (i = 0; i < pow(4,K); i++) {
		ll a = A, b = B, c = C;
		vl B = bitList(4, K, i);
		for (j = 0; j < K; j++) {
			if (B[j] == 0) a *= 2;
			else if (B[j] == 1) b *= 2;
			else if(B[j]==2) c *= 2;
		}
		if (b > a && c > b) {
			cout << "Yes" << endl;
			exit(0);
		}
	}
	cout << "No" << endl;
}

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

using namespace std;

#define N 105
 
int n, K, i, m, x, a[N], j, ans;

int main (void)
{
	scanf("%d%d",&n,&K);
	for (i=1; i<=K; i++) {
		scanf("%d",&m);
		for (j=1; j<=m; j++) scanf("%d",&x),a[x]=1;
	} 
	ans=0;
	for (i=1; i<=n; i++) if (!a[i]) ans++;
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 3756
#include <vector>
#include <iostream>
#include <set>
#include <cstdio>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <ctime>
#include <cmath>
#include <complex>
#include <algorithm>
#include <tuple>
#include <algorithm>
#include <limits>
#include <map>

using namespace std;

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

int d[110], f[110];
vector<int> g[110];
int t;
bool used[110];
void solve(int i) {
    if (used[i]) return;
    used[i] = true;
    t++;
    d[i] = t;
    for (int j: g[i]) {
        solve(j);
    }
    t++;
    f[i] = t;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int id, u;
        cin >> id >> u;
        for (int j = 0; j < u; j++) {
            int a;
            cin >> a;
            g[i].push_back(a-1);
        }
    }
    t = 0;
    fill_n(used, 110, false);
    for (int i = 0; i < n; i++) {
        solve(i);
    }
    for (int i = 0; i < n; i++) {
        printf("%d %d %d\n", i+1, d[i], f[i]);
    }
    return 0;
}

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

using namespace std;

int main() {
  int K, S;
  cin >> K;
  cin >> S;
  int ans = 0;

  for (int i = 0; i <= K; i++) {
    for (int j = 0; j <= K; j++) {
      if (S - i - j <= K && S - i - j >= 0) {
        ans++;
      }
    }
  }

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

Measured memory_bytes: 256
#include <iostream>
#include <vector>
//#include <string>
#include <algorithm>
//#include <math.h>
//#include <queue>
//#include <stack>
//#include <iomanip>

// sometimes used
//#include <set>
//#include <map>
//#include <numeric>
//#include <list>
//#include <deque>
//#include <unordered_map>

typedef long long LL;
//typedef long double LD;
using namespace std;
 
//#define MOD 1000000007
//#define MAX 100100
//#define NIL -1
//#define INFTY 1000000000000000000

int main(){
    LL r;
    LL c;
    LL k;
    cin >> r >> c >> k;
    vector<vector<LL>> v(r, vector<LL>(c, 0));
    LL tmp_r;
    LL tmp_c;
    LL tmp_v;
    for(LL i=0; i<k; i++){
        cin >> tmp_r >> tmp_c >> tmp_v;
        tmp_r--;
        tmp_c--;
        v[tmp_r][tmp_c]=tmp_v;
    }
    vector<vector<vector<LL>>> dp(r, vector<vector<LL>>(c,vector<LL>(4,0)));
    dp[0][0][1]=dp[0][0][0]+v[0][0];
    for(LL i=0; i<r; i++){
        for(LL j=0; j<c; j++){
            for(LL l=0; l<4; l++){
                if(i!=0){
                    dp[i][j][0]=max(dp[i][j][0], dp[i-1][j][l]);
                }
            }
            if(v[i][j]!=0){
                dp[i][j][1]=dp[i][j][0]+v[i][j];
            }
            for(LL l=0; l<4; l++){
                if(j!=0){
                    dp[i][j][l]=max(dp[i][j][l], dp[i][j-1][l]);
                    if(v[i][j]!=0 && l>=1){
                        dp[i][j][l]=max(dp[i][j][l], dp[i][j-1][l-1]+v[i][j]);
                    }
                }
            }
        }
    }

    LL max_ans=0;
    for(LL i=0; i<4; i++){
        max_ans=max(max_ans, dp[r-1][c-1][i]);
    }

    cout << max_ans << endl;

    return 0;
}


Measured memory_bytes: 706704
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <functional>
#include <numeric>
#include <iostream>
#include <string>
#include <time.h>

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }

int n,p[234];

int main() {

	scanf("%d", &n);
	rep(i, n) scanf("%d", &p[i]);

	int C = 0;
	rep(i, n - 2) {
		if ((p[i] < p[i + 1] && p[i + 1] < p[i + 2]) || (p[i] > p[i + 1] && p[i + 1] > p[i + 2])) C++;
	}

	printf("%d\n", C);


	return 0;
}


Measured memory_bytes: 256
import math
n = int(input())
x = list(map(int,input().split()))
y = list(map(int,input().split()))
L1,L2,L3 = 0.0,0.0,0.0
L = []
for i in range(n):
    L1 += abs(x[i]-y[i])
    L2 += (x[i]-y[i])**2
    L3 += abs(x[i]-y[i])**3
    L .append(abs(x[i]-y[i]))
print(L1)
print(math.sqrt(L2))
print(math.pow(L3, 1.0/3.0))    
print(max(L))


Measured memory_bytes: 5700
from collections import deque

icase=0
if icase==0:
    n,q=map(int,input().split())
    g = [set() for _ in range(n)]
    for i in range(n-1):
        ai,bi=map(int,input().split())
        g[ai-1].add(bi-1)
        g[bi-1].add(ai-1)
    g=tuple(g)
    xx=[0]*n
    for i in range(q):
        pi,xi=map(int,input().split())
        xx[pi-1]=xx[pi-1]+xi
elif icase==2:
    n,q=4,3
    g = [deque([]) for _ in range(n)]
    g[0]=deque([1])
    g[1]=deque([0,2,3])
    g[2]=deque([1])
    g[3]=deque([1])
    p=[0]*q
    x=[0]*q
    p[0]=1
    x[0]=10    
    p[1]=0
    x[1]=100
    p[2]=2
    x[2]=1    
    xx=[0]*n
    for i in range(q):
        xx[p[i]]=xx[p[i]]+x[i]
#ans:100 110 111 110
elif icase==3:
    n,q=6,2
    g = [deque([]) for _ in range(n)]
    g[0]=deque([1,2])
    g[1]=deque([0,3,4])
    g[2]=deque([0,5])
    g[3]=deque([1])
    g[4]=deque([1])
    g[5]=deque([2])
    p=[0]*q
    x=[0]*q
    p[0]=0
    x[0]=10    
    p[1]=0
    x[1]=10    
    xx=[0]*n
    for i in range(q):
#        pi,xi=map(int,input().split())
        xx[p[i]]=xx[p[i]]+x[i]
        
#q = deque([0])
stack=[0]
parent=[-1]*n
while stack:
#    print(q)
    state = stack.pop()
#    print("------------- stack:",stack,"state:",state,"g:",g[state])
    for v in g[state]:
#        print("state:",state,"v:",v,"q:",q)
        if parent[state] == v:
            continue
        else:
            parent[v]=state
            stack.append(v)
            xx[v]+=xx[state]
#            print("parent:",parent,"xx:",xx,"stack",stack)

print(" ".join(map(str,xx[0: ])))


Measured memory_bytes: 93452
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<string> VS;
typedef vector< vector<int> > VVI;
typedef vector< vector<ll> > VVL;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
 
int main(){
  int N;
  cin>>N;
  VI A(N);
  rep(i,N) cin>>A[i];
  sort(all(A));
  if(N%2){
    if(A[0]!=0){
      cout<<0<<endl;
      return 0;
    }
    rep(i,N/2){
      if(A[1+i*2]!=(i+1)*2 or A[2+i*2]!=(i+1)*2){
        cout<<0<<endl;
        return 0;
      }
    }
    ll ans=1;
    ll mod=1e9+7;
    rep(i,N/2) (ans*=2)%=mod;
    cout<<ans<<endl;
    return 0;
  }
  rep(i,N/2){
    if(A[i*2]!=i*2+1 or A[i*2+1]!=i*2+1){
      cout<<0<<endl;
      return 0;
    }
  }
  ll ans=1;
  ll mod=1e9+7;
  rep(i,N/2) (ans*=2)%=mod;
  cout<<ans<<endl;
}

Measured memory_bytes: 768
import java.util.Scanner;

/**
 * Created by ??\??? on 2016/12/6.
 */
public class Main {
    static int si(String s){
        return Integer.parseInt(s);
    }

    static int run(String[] args){
        Scanner scan  = new Scanner(System.in);
        int T = si(scan.nextLine());
        int sum = 0;
        String[] lines = scan.nextLine().split(" ");
        for(int i = 0;i < lines.length;i++){
            int min = i;
            for(int j = i+1;j<lines.length;j++){
                if(si(lines[min])>si(lines[j])){
                    min = j;

                }
            }
            if(min!=i) {
                String s = lines[i];
                lines[i] = lines[min];
                lines[min] = s;
                sum++;
            }
        }
        for(int i = 0;i<lines.length;i++){
            if(i==0)
                System.out.print(lines[0]);
            else
                System.out.print(" "+lines[i]);
        }
        System.out.println();
        System.out.println(sum);
        return 0;
    }
    public static void main(String[] args){
        run(args);
    }

}

Measured memory_bytes: 26988
#include <bits/stdc++.h>
using namespace std;
 
/*** Template Begins ***/
#define ll          long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        1000000007
#define rep(i,a,b)  for(int i=a;i<b;i++)
 
// Debug //
 
#define trace(x)                 cerr << #x << ": " << x << endl;
#define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;

/*** Template Ends ***/
#define int long long
int modexpo(int x,int y)
{
    x %= hell;
    int res = 1;
    while(y){
        if(y&1) res = (res*x)%hell;
        x = (x*x)%hell;
        y = y/2;
    }
    return res;
}

void solve(){
    int n;
    cin>>n;
    int sum=0,sq=0,ans=0,a;
    rep(i,0,n){
        cin>>a;
        sq=(sq+(a*a)%hell)%hell;
        sum=(sum+a)%hell;
    }
    ans=(sum*sum%hell - sq + hell)%hell;
    ans=(ans * modexpo(2,hell-2))%hell;
    cout<<ans<<endl;
}
 
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

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

using ll  = long long;
using pii = pair<int,int>;
#define dbg(n) cout<<'\n'<<#n<<" is "<<n<<'\n';
#define pb push_back
#define all(v) v.begin(), v.end()
#define cs(i) cout<<"Case "<<i+1<<": \n"; 
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);

const int N   = 1e5+5;
const int INF = 0x7fffffff;

ll dp[105][N],we[N],c[N],capacity,n;

ll func(int i,int w){
    if(i>=n)
        return 0;
    ll profit1=0,profit2=0;
    if(dp[i][w]!=-1)
        return dp[i][w];
    if(w+we[i]<=capacity)
        profit1=func(i+1,we[i]+w)+c[i];
    else
        profit1=0;
    profit2=func(i+1,w); //dbg(profit2) dbg(profit1)
    return dp[i][w]=max(profit1,profit2);
}

int main(){
    int t,hold=0;

    cin>>n;
    cin>>capacity;
    memset(dp,-1,sizeof dp);
    for(int i=0;i<n;i++)
        cin>>we[i]>>c[i];
    cout<<func(0,0);
    return 0;
}

Measured memory_bytes: 82304
//abc051_c.cpp
//Tue Jun  5 22:35:00 2018

#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
using ll=long long;

int main(){
	int sx,sy,tx,ty;
	cin >> sx >> sy >> tx >> ty;

	for (int i=sx;i<tx;i++){
		cout << "R";
	}

	for (int i=sy;i<ty;i++){
		cout << "U";
	}

	for (int i=tx;i>sx;i--){
		cout << "L";
	}

	for (int i=ty;i>sy;i--){
		cout << "D";
	}

	cout << "D";

	for (int i=sx;i<tx;i++){
		cout << "R";
	}

	cout << "R" << "U";

	for (int i=sy;i<ty;i++){
		cout << "U";
	}

	cout << "L" << "U";

	for (int i=tx;i>sx;i--){
		cout << "L";
	}

	cout << "L" << "D";

	for (int i=ty;i>sy;i--){
		cout << "D";
	}

	cout << "R" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
bitset<2000005>f;
int main()
{
    f[0]=1;
	int n,a,s=0;
	bool b=0;
    cin>>n;
    while(cin>>a)
    {
        f|=f<<a;
        s+=a;
    }
    for(register int i=int(ceil(s*1.0/2));i<=s;i++)
	{
        if(f[i])
		{
			cout<<i<<endl;
			b=1;
		}
		if(b==1)
			return 0;
    }
    return 0;
}

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

using namespace std;

int main()
{
    int n,v[21],c[21],ans=0;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    for(int i=0;i<n;i++){
        cin>>c[i];
    }
    for(int i=0;i<n;i++){
        if(v[i]-c[i]>=0){
            ans+=(v[i]-c[i]);
        }
    }
    cout<<ans;
    return 0;
}


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

using namespace std;

typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define debug(a) cout << #a << ": " << a << endl;

int main() {
  int A, B, C;
  cin >> A >> B >> C;
  int maxNum = max({A, B, C});
  cout << maxNum * 10 + A + B + C - maxNum << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <bitset>
#include <complex>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <queue>

using namespace std;

struct BoolName : numpunct<char> {
  string t, f;
  BoolName (string t = "Yes", string f = "No") : t(t), f(f) {}
  string do_truename() const {return t;}
  string do_falsename() const {return f;}
};

struct Initializer {
  Initializer() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(15) << boolalpha;
    cout.imbue(locale(cout.getloc(), new BoolName));
  }
} initializer;

template<typename T> istream& operator>>(istream &s, vector<T> &v) {
  for (T &t : v) s >> t;
  return s;
}

template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
  for (const T &t : v) s << t << endl;
  return s;
}

void set_bool_name(string t, string f) {
  cout.imbue(locale(cout.getloc(), new BoolName(t, f)));
}

template<typename T> bool chmin(T& a, T b) {return a > b ? a = b, true : false;}

template<typename T> bool chmax(T& a, T b) {return a < b ? a = b, true : false;}

template<typename T> void sort(vector<T>& v) {sort(v.begin(), v.end());}

int main() {
  int64_t h, w, res = numeric_limits<int64_t>::max();
  cin >> h >> w;
  for (int k = 0; k < 2; ++k) {
    if (h % 3 == 0) {
      cout << 0 << endl;
      return 0;
    }
    if (h >= 3) chmin(res, w);
    for (int i = 1; i < h; ++i) {
      auto a = i * w;
      auto b = (h - i) * (w / 2);
      auto c = (h - i) * ((w + 1) / 2);
      chmin(res, max({a, b, c}) - min({a, b, c}));
    }
    swap(h, w);
  }
  cout << res << endl;
}



Measured memory_bytes: 256
n = int(input())
xl = []
for i in range(n):
    xl.append(list(map(int,input().split())))
    xl[i].append(xl[i][0]+xl[i][1])
xl = sorted(xl,key=lambda x:x[2])
ans = 1
s = xl[0][2]
for i in range(1,n):
    if s <= xl[i][0]-xl[i][1]:
        s = xl[i][2]
        ans += 1
print(ans)

Measured memory_bytes: 33064
//#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a);i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"ayaya~"<<endl
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
gpu_hash_table<int, int> mp;
#define ordered_set tree<ttgl, null_type,less<ttgl>, rb_tree_tag,tree_order_statistics_node_update>
 */
using ll = long long;
using ld = long double;
const ll MOD = 924844033;
const ll root = 62;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll modInv(ll a){return binpow(a, MOD-2);}
const double PI = acos(-1);
const double eps = -1e6;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
const int mxN = 1001;
int n, k;
ll arr[mxN];
ll sum[mxN*mxN];
int cnt = 0;
int main() {
    //freopen("file.in", "r", stdin);
    //freopen("file.out", "w", stdout);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>k;
    owo(i, 1, n+1) {
        cin>>arr[i];
        arr[i]+=arr[i-1];
    }
    owo(i, 0, n) owo(j, i, n) {
      sum[cnt++] = arr[j+1]-arr[i];
    }
    ll ans = 0;
    uwu(bit, 41, 0) {
      ans+=(1LL<<bit);
      int num = 0;
      owo(i, 0, cnt) {
        if((sum[i]&ans)==ans)num++;
      }
      if(num<k) {
        ans-=1LL<<bit;
      }
    }
    cout<<ans<<"\n";
    return 0;
}

Measured memory_bytes: 7440
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
n,t = map(int,readline().split())
f = []
m = 0
for i in range(n):
  p,q = map(int,readline().split())
  m = max(m,p)
  f.append((p,q))
  
f.sort()
dp = [[0]*(t+m) for i in range(n+1)]

for i,c in enumerate(f):
  a,b = c
  for j in range(t+m):
    if j < a or j-a >= t:
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = max(dp[i][j],dp[i][j-a]+b)
      
print(max(dp[n]))

Measured memory_bytes: 181212
N, M = map(int, input().split())

A = [True for i in range(N + 1)]

dp = [0 for i in range(N + 2)]

for i in range(M):
    a = int(input())
    A[a] = False

dp[0] = 1
for i in range(N):
    if A[i] == 0:
        continue
    dp[i + 1] += dp[i]
    dp[i + 1] %= 1000000007
    dp[i + 2] += dp[i]
    dp[i + 2] %= 1000000007

print(dp[N])


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

using namespace std;

int main(int argc, const char *argv[]) {
  int n, c;
  cin >> n >> c;

  vector<vector<int>> vd(c, vector<int>(c));
  for (int i = 0; i < c; ++i) {
    for (int j = 0; j < c; ++j) {
      cin >> vd[i][j];
    }
  }

  // mod % 3がmで，色がcのマスの数: vm[m][c]
  vector<vector<int>> vm(3, vector<int>(c, 0));
  vector<vector<int>> vc(n, vector<int>(n));
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      int c;
      cin >> c;
      c--;
      vc[i][j] = c;
      vm[(i + j + 2) % 3][c]++;
    }
  }

  int ans = -1;
  for (int i = 0; i < c; ++i) {
    for (int j = 0; j < c; ++j) {
      if (i == j) {
        continue;
      }

      for (int k = 0; k < c; ++k) {
        if (j == k || i == k) {
          continue;
        }

        // mod%3=0,1,2にそれぞれi, j, kを割り当てる
        // 元の色がl
        int d = 0;
        for (int l = 0; l < c; ++l) {
          d += vm[0][l] * vd[l][i];
          d += vm[1][l] * vd[l][j];
          d += vm[2][l] * vd[l][k];
        }

        if (ans < 0 || d < ans) {
          ans = d;
        }
      }
    }
  }

  cout << ans << '\n';

  return 0;
}

Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std;
#define pi 3.14159265359
#define int long long
#define pii pair<int,int>
const int mod=1e9+7;
 
int dx[]={-1,0,1,0};
int dy[]={0,-1,0,1};



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

   


int n;
cin>>n;
vector<int>v(n);

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

int ans=1e18;
for(int i=1;i<=100;i++)
{
   int val=0;
   for(int j=0;j<n;j++)
   {
      val+=(v[j]-i)*(v[j]-i);
   }
   ans=min(ans,val);
}
cout<<ans;


}



Measured memory_bytes: 256
N,M = map(int,input().split())

ab = []
ans = 0

for i in range(M):

    a,b = map(int,input().split())
    ab.append([a,b])

for i in range(M):

    abc = ab.copy()
    del abc[i]

    lis = [1] + [0] * (N-1)

    flag = True

    while flag:

        flag = False

        for j in abc:

            if lis[ j[0]-1 ] == 1:
                lis[ j[1]-1 ] = 1
                abc.remove(j)
                flag = True
                break

            elif lis[ j[1]-1 ] == 1:
                lis[ j[0]-1 ] = 1
                abc.remove(j)
                flag = True
                break

    #print (lis)
    if 0 in lis:
        ans += 1

print (ans)

            

    


Measured memory_bytes: 3064
s=list(input())

for i in range(len(s)):
    if(s[i]=="B"):
        s[i]="A"
        for j in range(i,-1,-1):
            if((s[j]=="0")|(s[j]=="1")):
                s[j]="A"
                break

for C in s:
    if(C!="A"):
        print(C,end="")



Measured memory_bytes: 3060
import java.util.*;

public class Main {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
     int N = sc.nextInt();
     Integer A[] = new Integer[N];
		for (int i=0; i<N; i++) {
			A[i] = sc.nextInt();
		}
		
    for(int i=0; i<N; i++) {
    	if(A[i] % 2 == 0) {
    		if((A[i] % 3 != 0) && (A[i] % 5 != 0)) {
    			System.out.println("DENIED");
    			return;
    		}
    	}
    }
    System.out.println("APPROVED");
	}
	}

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

int M, T, P, R;
int wa[52][12];
int ac[52], pe[52], id[52];

int main(){
  while(cin >> M >> T >> P >> R){
    if(M == 0) break;

    memset(ac, 0, sizeof(ac));
    memset(wa, 0, sizeof(wa));
    memset(pe, 0, sizeof(pe));

    while(R--){
      int m, t, p, j;
      cin >> m >> t >> p >> j;

      t--;
      p--;

      if(j == 0){
        ac[t]++;
        pe[t] += m;
        pe[t] += 20 * wa[t][p];
      }
      else{
        wa[t][p]++;
      }
    }

    for(int i = 0; i < T; i++){
      id[i] = i + 1;
    }
    for(int i = 0; i < T; i++){
      for(int j = i + 1; j < T; j++){
        if(ac[i] < ac[j] || ac[i] == ac[j] && pe[i] > pe[j] ||
           ac[i] == ac[j] && pe[i] == pe[j] && id[i] < id[j]){
          swap(ac[i], ac[j]);
          swap(pe[i], pe[j]);
          swap(id[i], id[j]);
        }
      }
    }

    cout << id[0];
    for(int i = 1; i < T; i++){
      if(ac[i - 1] == ac[i] && pe[i - 1] == pe[i]) cout << "=";
      else                                         cout << ",";

      cout << id[i];
    }
    cout<<endl;
  }
}

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


def solve(N: int, S: "List[str]", P: "List[int]"):
    merged_list = [[i+1,s,p] for i, (s, p) in enumerate(zip(S, P))]
    merged_list = sorted(merged_list, key = lambda x:(x[1], -x[2]))
    for i in range(N):
        print(merged_list[i][0])
    return


# Generated by 1.1.4 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()
    N = int(next(tokens))  # type: int
    S = [str()] * (N)  # type: "List[str]" 
    P = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        S[i] = next(tokens)
        P[i] = int(next(tokens))
    solve(N, S, P)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for(ll i=0; i<(ll)n; i++)
#define REPR(i, n) for(ll i=(ll)n-1; i>=0; i--)
#define FOR(i, m, n) for(ll i=(ll)m; i<(ll)n; i++)
#define FORR(i, m, n) for(ll i=(ll)m-1; i>=(ll)n; i--)
#define ALL(x) (x).begin(), (x).end()
#define ASC(v) sort(ALL(v));
#define DESC(v) sort(ALL(v), greater<int>());
#define UNIQ(a) sort(ALL(a));(a).resize(unique(ALL(a)) - a.begin());
#define PRINTD(x, d) cout << fixed << setprecision(d) << x << "\n";
#define DEBUG(x) cout<<#x<<": "<<x<<"\n"
const double PI = acos(-1);
ll lcm(ll a, ll b) { return a / __gcd(a, b) * b; }
bool isprime(int x){ int i; if(x<2)return 0; else if(x==2) return 1; if(x%2==0) return 0; for(i=3; i*i<=x; i+=2) if(x%i==0) return 0; return 1; }
int digsum(int n) { int r=0; while(n>0) { r+=n%10; n/=10; } return r; }
vector<string> split(string s, char p){vector<string>v;stringstream m(s);string b;while(getline(m,b,p))v.push_back(b);return v;}
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 (a>b) { a = b; return 1; } return 0; }
struct nya{ nya(){ cin.tie(0); ios::sync_with_stdio(false); } }nyan;

int main(){
    ll N, M, K; cin >> N >> M >> K;
    vector<ll> a(N+1,0), b(M+1,0);
    REP(n, N) {
        ll t; cin >> t;
        a[n+1] = t + a[n];
    }
    REP(m, M) {
        ll t; cin >> t;
        b[m+1] = t + b[m];
    }

    if (a[N]+b[M] <= K) {
        cout << N+M << "\n";
        return 0;
    }

    ll ans = 0;
    REP(n, N+1) {
        if(a[n] > K) break;
        ll l=0, r=M+1;
        ll m;
        while (l < r) {
            m = (l+r)/2;
            if (a[n]+b[m]<=K && a[n]+b[m+1]>K) break;
            if (a[n]+b[m] <= K) l = m+1;
            if (a[n]+b[m] > K) r = m;
        }
        chmax(ans, n+m);
    }
    cout << ans << "\n";
}


Measured memory_bytes: 6336
h,w = map(int, input().split())
ch, cw = map(int, input().split())
ch -= 1
cw -= 1
dh,dw = map(int, input().split())
dh -= 1
dw -= 1

def trans(s):
    res = []
    for i in s:
        if i == '.':
            res.append(-1)
        else:
            res.append(-2)
    return res

def move(x,y,dq,dq_next):
    for ix,iy in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
        if ix > h-1 or ix < 0 or iy > w-1 or iy < 0:
            continue
        if (m[ix][iy] == -1) or (m[ix][iy] > m[x][y]):
            m[ix][iy] = m[x][y]
            dq.append((ix, iy))
    for ix, iy in [(x-2, y-2), (x-2, y-1), (x-2, y), (x-2, y+1), (x-2, y+2),
                        (x-1, y-2), (x-1, y-1), (x-1, y+1), (x-1, y+2),
                        (x, y-2), (x, y+2),
                        (x+1, y-2), (x+1, y-1), (x+1, y+1), (x+1, y+2),
                        (x+2, y-2), (x+2, y-1), (x+2, y), (x+2, y+1), (x+2, y+2)]:
        if ix > h-1 or ix < 0 or iy > w-1 or iy < 0:
            continue
        if m[ix][iy] == -1:
            m[ix][iy] = m[x][y] + 1
            dq_next.append((ix, iy))
            
m = [trans(input()) for _ in range(h)]

from collections import deque

m[ch][cw] = 0

def main():
    dq = deque()
    dq_next = deque()
    dq.append((ch,cw))
    while True:
        while len(dq)>0:
            xx, yy = dq.popleft()
            if xx == dh and yy == dw:
                return m[xx][yy]
            move(xx, yy, dq, dq_next)
        if len(dq_next) > 0:
            dq = dq_next.copy()
            dq_next = deque()
        else:
            return -1
          
print(main())

Measured memory_bytes: 96552
#include <stdio.h>
int main(void){
    char c;
    int x[26]={0}, i;
    while (scanf("%c", &c) != EOF){
        int num1 = c - 'a';
        for(i=0; i<26; i++){
            if(num1 == i) x[i]++;
        }
        
        int num2 = c - 'A';
        for(i=0; i<26; i++){
            if(num2 == i) x[i]++;
        }
    }
    
    for(i=0; i<26; i++){
        printf("%c : %d\n", i+'a', x[i]);
    }
    
    return 0;
}


Measured memory_bytes: 2060
#include<bits/stdc++.h>
using namespace std;
long long a[86];
int main()
{
	
	char x,y;
	cin>>x>>y;
	if(x>y)cout<<">"<<endl;
	else if(x<y) cout<<"<"<<endl;
	else cout<<"="<<endl;
	
	
	
}

Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1145141919810893364
//#define INF 810114514
#define PI 3.141592653589
typedef long long ll;
typedef pair<ll,ll> PP;
#define int ll
#define setdouble setprecision
#define REP(i,n) for(int i=0;i<(n);++i)
#define OREP(i,n) for(int i=1;i<=(n);++i)
#define RREP(i,n) for(int i=(n)-1;i>=0;--i)
#define GOODBYE do { cout << "0" << endl; return 0; } while (false)
#define MM <<" "<<
#define Endl endl
#define debug false
#define debug2 false

int N,M,Q;
vector<int> a,b,c,d;
int Ans;

void saku(vector<int> A){
    
    /*REP(i,A.size()){
        cout << A[i] << " ";
    }cout << endl;*/
    
    if(A.size()<N){
        vector<int> As;
        int f=1;
        if(A.size()>0)f=A[(int)(A.size())-1];
        for(int i=f;i<=M;i++){
            As=A;
            As.push_back(i);
            saku(As);
        }
    }else{
        int num=0;
        REP(i,Q){
            if(A[b[i]]-A[a[i]]==c[i]){
                num+=d[i];
            }
        }
        Ans=max(Ans,num);
    }
}

signed main(void){
    
    int q;
    cin >> N >> M >> Q;
    
    REP(i,Q){
        cin >> q;q--;a.push_back(q);
        cin >> q;q--;b.push_back(q);
        cin >> q;c.push_back(q);
        cin >> q;d.push_back(q);
    }
    
    Ans=-INF;
    vector<int> emp;
    emp.clear();
    saku(emp);
    cout << Ans << endl;
    
    
    return 0;
}




Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
#define D10 fixed<<setprecision(10)
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
const int MOD = 1000000007;
const int INF = MOD + 1;
const ld EPS = 1e-10;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/

int main()
{
	int n, m;
	cin >> n >> m;
	vs fld(n);
	REP(i, n) cin >> fld[i];
	vector<vector<pii>> v(26);
	REP(i, n)REP(j, m)
	{
		if (fld[i][j] != '.')
		{
			v[fld[i][j] - 'A'].emplace_back(i, j);
		}
	}
	bool update = true;
	int ans = 0;
	while (update)
	{
		update = false;
		REP(i, 26)
		{
			if (v[i].size() == 0) continue;
			int ax = v[i][0].first, ay = v[i][0].second;
			int bx = v[i][1].first, by = v[i][1].second;
			if (ax == bx)
			{
				bool f = true;
				if (ay > by) swap(ay, by);
				FOR(j, ay + 1, by)
				{
					if (fld[ax][j] != '.') f = false;
				}
				if (f&&abs(ay-by)>1)
				{
					update = true;
					v[i].clear();
					ans++;
					fld[ax][ay] = fld[bx][by] = '.';
				}
			}
			else if (ay == by)
			{
				bool f = true;
				if (ax > bx) swap(ax, bx);
				FOR(j, ax + 1, bx)
				{
					if (fld[j][ay] != '.') f = false;
				}
				if (f&&abs(ax - bx)>1)
				{
					update = true;
					v[i].clear();
					ans++;
					fld[ax][ay] = fld[bx][by] = '.';
				}
			}
			else
			{
				if (ay > by)
				{
					swap(ax, bx), swap(ay, by);
				}
				if (ax > bx)
				{
					bool f1 = true;
					FOR(j, ay + 1, by)
					{
						if (fld[ax][j] != '.') f1 = false;
					}
					FOR(j, bx + 1, ax + 1)
					{
						if (fld[j][by] != '.') f1 = false;
					}
					bool f2 = true;
					FOR(j, bx, ax)
					{
						if (fld[j][ay] != '.') f2 = false;
					}
					FOR(j, ay, by)
					{
						if (fld[bx][j] != '.') f2 = false;
					}
					if (f1 || f2)
					{
						update = true;
						v[i].clear();
						ans++;
						fld[ax][ay] = fld[bx][by] = '.';
					}
				}
				if (ax < bx)
				{
					bool f1 = true;
					FOR(j, ay + 1, by+1)
					{
						if (fld[ax][j] != '.') f1 = false;
					}
					FOR(j, ax, bx)
					{
						if (fld[j][by] != '.') f1 = false;
					}
					bool f2 = true;
					FOR(j, ax+1, bx)
					{
						if (fld[j][ay] != '.') f2 = false;
					}
					FOR(j, ay, by)
					{
						if (fld[bx][j] != '.') f2 = false;
					}
					if (f1 || f2)
					{
						update = true;
						v[i].clear();
						ans++;
						fld[ax][ay] = fld[bx][by] = '.';
					}
				}
			}
		}
	}
	cout << ans * 2 << endl;
	return 0;
}

Measured memory_bytes: 3340
import itertools

time = []
best_time = 10**9
for i in range(5): time.append(int(input()))

def next_time(t):
    if t%10 == 0: return t
    else: return (t//10+1)*10

for v in itertools.permutations(time):
    total_time = 0
    for i in range(5):
        if i == 4: total_time += v[i]
        else: total_time += next_time(v[i])
    best_time = min(best_time, total_time)
    
print(best_time)

Measured memory_bytes: 3060
import java.util.*

fun main(args: Array<String>) {
    val pw = java.io.PrintWriter(System.out)
    Problem.solve(Scanner(System.`in`), pw)
    pw.flush()
}

fun <A : Comparable<A>> min(a: A, b: A) = if (a < b) a else b

object Problem {
    fun solve(sc: Scanner, pw: java.io.PrintWriter) {
        val N = sc.next().toInt()
        val M = sc.next().toInt()
        val X = sc.next().toInt()
        var l = 0
        var r = 0
        repeat(M) {
            val A = sc.next().toInt()
            if (X < A) l++
            else r++
        }
        pw.println(min(l, r))
    }
}


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

#define LL long long
#define LD long double
#define SC(t,x) static_cast<t>(x)
#define AR(t) vector < t >
#define PII pair < int, int >
#define PLL pair < LL, LL >
#define PIL pair < int, LL >
#define PLI pair < LL, int >
#define MP make_pair
#define PB push_back
#define PF push_front
#define POB pop_back
#define POF pop_front
#define PRF first
#define PRS second
#define INIT(ar,val) memset ( ar, val, sizeof ( ar ) )
#define lp(loop,start,end) for ( int loop = start; loop < end; ++loop )
#define lpd(loop,start,end) for ( int loop = start; loop > end; --loop )
#define lpi(loop,start,end) for ( int loop = start; loop <= end; ++loop )
#define lpdi(loop,start,end) for ( int loop = start; loop >= end; --loop )
#define qmax(a,b) (((a)>(b))?(a):(b))
#define qmin(a,b) (((a)<(b))?(a):(b))
#define qabs(a) (((a)>=0)?(a):(-(a)))

const int INF = 0x3fffffff;
const int SINF = 0x7fffffff;
const long long LINF = 0x3fffffffffffffff;
const long long SLINF = 0x7fffffffffffffff;
const int MAXN = 200007;
const int MOD = 998244353;

int n;
char s[MAXN];
int dp[MAXN];
map < int, int > mp;

void init ();
void input ();
void work ();

int getc ( int l );
int getdp ( int l );

int add ( int x, int y )
{
	return ( ( x += y ) < MOD ) ? x : ( x - MOD );
}

void addv ( int &x, int y )
{
	( ( x += y ) < MOD ) ? x : ( x -= MOD );
}

int sub ( int x, int y )
{
	return ( ( x -= y ) >= 0 ) ? x : ( x + MOD );
}

void subv ( int &x, int y )
{
	( ( x -= y ) >= 0 ) ? x : ( x += MOD );
}

int qpow ( int a, int b )
{
	LL base = a, ans = 1;
	while ( b ) {
		if ( b & 1 ) ( ans *= base ) %= MOD;
		( base *= base ) %= MOD;
		b >>= 1;
	}
	return SC ( int, ans );
}



int main ()
{
	init ();
	input ();
	work ();
}



void init ()
{
	// Init Everything Here

	ios::sync_with_stdio ( false );
}

void input ()
{
	// input method

	scanf ( "%d%s", &n, s );
}

void work ()
{
	// main work

	lpi ( i, 1, n ) {
		if ( ( ( n % i ) == 0 ) && ( ( n / i ) & 1 ) ) {
			mp[i] = getc ( i );
		}
	}

	int ans = 0;
	lpi ( i, 1, n ) {
		if ( ( ( n % i ) == 0 ) && ( ( n / i ) & 1 ) ) {
			addv ( ans, SC ( LL, getdp ( i ) ) * i % MOD );
		}
	}
	addv ( ans, ans );
	cout << ans << endl;
}



int getc ( int l )
{
	int ans = 0;
	lp ( i, 0, l ) {
		addv ( ans, ans );
		addv ( ans, s[i] - '0' );
	}
	char nt;
	bool flag = true;
	lp ( i, 0, n ) {
		nt = s[i%l];
		if ( ( i / l ) & 1 ) {
			nt ^= '0' ^ '1';
		}
		if ( nt < s[i] ) {
			break;
		} else if ( nt > s[i] ) {
			flag = false;
			break;
		}
	}
	if ( flag ) addv ( ans, 1 );
	return ans;
}

int getdp ( int l )
{
	INIT ( dp, 0 );
	int nc;
	lpi ( i, 1, l ) {
		if ( mp.find ( i ) != mp.end () ) {
			nc = mp[i];
			addv ( dp[i], nc );
			for ( int j = i << 1; j <= l; j += i ) subv ( dp[j], dp[i] );
		}
	}
	return dp[l];
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
#ifdef HIRO
#define d(f_, ...) printf((f_), ##__VA_ARGS__)
#else
#define d(f_, ...)
#endif

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pllll;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector< pair<int, int> > vii;
typedef vector< pair<long long, long long> > vllll;
typedef map<int, int> mii;
typedef map<long long, long long> mllll;
typedef queue<int> qi;
typedef queue< pair<int, int> > qp;
#define mp make_pair
#define pi 3.14159265358979323846
#define MAX max_element
#define MIN min_element
#define all(v) v.begin(), v.end()
#define gt(T) greater<T>()
#define sum(v) accumulate(v.begin(), v.end(), 0ll)
#define uni(v) do{ \
  sort(v.begin(), v.end()); \
  decltype(v)::iterator result = unique(v.begin(), v.end()); \
  v.erase(result, v.end()); \
}while(0)
#define fi(init, n) for(int i = init; i < n; ++i)
#define fj(init, n) for(int j = init; j < n; ++j)
#define fk(init, n) for(int k = init; k < n; ++k)
#define zero(x) memset(x, 0, sizeof(x))
#define negative(x) memset(x, ~0, sizeof(x))
#define bitsum(x) __builtin_popcount(x)
const ll MOD = 1e9 + 7;
const int INF = 1e9;
const int di[] = { 0, 1, 0, -1 };
const int dj[] = { 1, 0, -1, 0 };

template<typename T>
T gcd(T a, T b) {
	return b ? gcd(b, a % b) : a;
}
template<typename T>
T lcm(T a, T b) {
	return a / gcd(a, b) * b;
}
template<typename T>
int finder(vector<T> vec, T number) {
	auto itr = find(vec.begin(), vec.end(), number);
	size_t index = distance(vec.begin(), itr);
	if (index != vec.size()) return 1;
	else return 0;
}
ll frac(ll n){
	if (n == 0) return 1;
	return (n * frac(n - 1)) % MOD;
}
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(int argc, char** argv) {
#ifdef HIRO
  string quiz(argv[1]);
  string id(argv[2]);
  string filename("input/" + quiz + "/" + id + ".txt");
  ifstream fin(filename);
  if (fin.peek() == ifstream::traits_type::eof()) {
    cout << "No input.";
    return 0;
  }
  ifstream cin(filename);
  std::cin.rdbuf(cin.rdbuf());
#endif
  // ex: K = 7, T = 3
  //      1: 3
  //      2: 2
  //      3: 2
  //
  //     sort => 3, 2, 2
  //
  //     1 1 1
  //     2 2 3
  //     3
  //     => 1 2 3 1 2 1 3
  //
  // ex: K = 6, T = 3
  //      1: 1
  //      2: 4
  //      3: 1
  //
  //      sort => 4, 1, 1
  //
  //      2 2 2 2
  //      1 3
  //      => 2 1 2 3 2 2
  ll ans = 0;
  ll k, t;
  cin >> k >> t;
  int arr[t];
  fi(0, t)
    cin >> arr[i];

  sort(arr, arr + t, greater<int>());
  int cake[k];
  int width = arr[0];
  vector< vi > v(width);
  int cnt = 0;
  fi(0, t) {
    fj(0, arr[i]) {
      v[cnt % width].push_back(i);
      cnt++;
    }
  }
  cnt = 0;
  fi(0, width) {
    for(int x: v[i]) {
      // cout << x << " ";
      cake[cnt++] = x;
    }
    // cout << endl;
  }
  fi(1, k) {
    // cout << cake[i] << " ";
    if(cake[i] == cake[i - 1])
      ans++;
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 384
#include <bits/stdc++.h>
#define REP(i,s,e) for(int i=(s); i<(e);i++)
#define rep(i,n) REP(i,0,n)
#define rep1(i,n) REP(i,1,n)
#define repe(i,n) for(auto &&i:n)
#define all(v) (v).begin(),(v).end()
#define decimal fixed<<setprecision(20)
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)
using namespace std;
using LL = long long;
using Graph = vector<vector<int>>;
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 int INF = 1e9;
const LL LLINF = 1e16;

int w, d;
vector<vector<int>> cost;
queue<pair<int, int>> que;
set<pair<int, int>> st;


int bfs(){
    int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
    while(!que.empty()) {
        int x, y;
        tie(y, x) = que.front(); que.pop();
        for(int i = 0; i < 4; i++) {
            int ny = y+dy[i], nx = x+dx[i];
            if(nx < 0 || ny < 0 || nx >= w || ny >= d) continue;
            // cout << ny << " " << nx << endl;

            if(cost[ny][nx] < cost[y][x]-1){
                if(st.count(make_pair(ny, nx)) > 0){
                    return -1;
                }

                cost[ny][nx] = cost[y][x]-1;
                que.push(make_pair(ny, nx));
            }
        }
    }
    return 0;
}


int main(){
    fastcin();
    int n;
    cin >> w >> d >> n;
    cost.assign(d, vector<int>(w, -INF));
    rep(i, n){
        int x, y, z;
        cin >> x >> y >> z;
        x--; y--;
        st.insert(make_pair(y, x));
        que.push(make_pair(y, x));
        cost[y][x] = z;
    }
    if(bfs() == -1){
        cout << "No" << endl;
        return 0;
    }
    LL ans = 0;
    rep(i, d)rep(j, w){
        assert(cost[i][j] != -INF);
        ans += cost[i][j];
    }
    cout << ans << endl;
    return 0;



}


Measured memory_bytes: 3236
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define sz(x) (int)x.size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef vector<int> vi;
typedef long long ll;
typedef double db;

const int N = 200005;
int n, x, ans[N], vis[N], tmp[N], tn;

int main(){
	scanf("%d%d", &n, &x);
	if (x == 1 || x == 2 * n - 1) printf("No\n");
	else {
		memset(ans, 0, sizeof(ans));
		ans[n] = x; vis[x] = 1;
		ans[n - 1] = 1; ans[n + 1] = 2 * n - 1; vis[1] = vis[2 * n - 1] = 1;
		if (n != 2) {
			if (x == 2 * n - 2) {
				ans[n + 2] = 2; vis[2] = 1;
			} else {
				ans[n - 2] = 2 * n - 2; vis[2 * n - 2] = 1;
			}
			int j = 1;
			for (int i = 1; i <= 2 * n - 1; i++) {
				if (vis[i]) continue;
				while (ans[j]) j++;
				ans[j] = i;
			}
		}
		printf("Yes\n");
		for (int i = 1; i <= 2 * n - 1; i++) printf("%d\n", ans[i]);
	}
	return 0;
}



Measured memory_bytes: 2304