akhauriyash/Code-Regression huggingface dataset:
# ABC140E
class SegTree:
    def __init__(self, init_val, ide_ele, seg_func):
        self.segfunc = seg_func
        N = len(init_val)
        self.num = 2**(N-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(N):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
N, = map(int, input().split())
A = list(map(int, input().split()))
B = sorted([(a, i) for i, a in enumerate(A)], key=lambda x:x[0])
z = dict()
for i, (b, j) in enumerate(B):
    z[(b, j)] = i

ss = SegTree([3*N]*3*N, 3*N, min)
bs = []
y = 0
for i, x in enumerate(A):
    if i == 2*N:
        break
    ss.update(z[(x, i)], z[(x, i)])
    y += x
    if i < N-1:
        continue
    if i == N-1:
        bs.append(y)
    else:
        mx = ss.query(0, 3*N)
        y = y - B[mx][0]
        ss.update(mx, 3*N)
        bs.append(y)

ss = SegTree([-1]*3*N, -1, max)
nbs = []
#tmp = set()
y = 0
for i, x in enumerate(A[::-1]):
    if i == 2*N:
        break
    ss.update(z[(x, 3*N-i-1)], z[(x, 3*N-i-1)])
#    tmp.add((x, i))
    y += x
    if i < N-1:
        continue
    if i == N-1:
        nbs.append(y)
    else:
        mx = ss.query(0, 3*N)
#        print(max(tmp), B[mx])
#        tmp.remove(max(tmp))
        y = y - B[mx][0]
        ss.update(mx, -1)
        nbs.append(y)

#print(B)
#print(bs)
#print(nbs)
r = -10**18
for i in range(N+1):
    r = max(r, bs[i] - nbs[N-i])
print(r)


Measured memory_bytes: 126552
// C.

#include <algorithm>
#include <iostream>
#include <sstream>

using namespace std;
typedef long long LL;

int main(int argc, char *argv[])
{
	string s, t;
	cin >> s >> t;
	string ans;
	for (int i = s.length() - t.length(); i >= 0; --i) {
		bool ok = true;
		for (int j = 0; j < (int)t.length(); ++j) {
			if (s[i + j] != t[j] && s[i + j] != '?') {
				ok = false;
			}
		}
		if (ok) {
			string c = s.substr(0, i) + t + s.substr(i + t.length());
			replace(c.begin(), c.end(), '?', 'a');
			if (ans.empty() || ans > c) {
				ans = c;
			}
		}
	}
	cout << (ans.empty() ? "UNRESTORABLE" : ans) << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
 
using namespace __gnu_pbds;
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")

#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long int
#define ull unsigned long long
#define ld long double

#define mod 1000000007
#define EULER 2.7182818284
#define INF 1000000000

#define pb push_back
#define ins insert
#define IT iterator
#define PQ priority_queue
#define    nl           "\n"
#define fi first
#define se second
#define maxe max_element
#define mine min_element
#define er erase
#define lb lower_bound
#define ub upper_bound

#define vi vector<int>
#define vll vector<ll>
#define vb vector<bool>
#define pi pair<int,int>
#define pll pair<ll,ll>
#define all(v) v.begin(),v.end()

#define mem(v,i) memset(v,i,sizeof(v)) // v is array. To set all elements to 0 or -1 only. mem(arr,0);


#define repab(i,a,b) for(int i=(a);i<=(b);i++)
#define reprab(i,a,b) for(int i=(a);i>=(b);i--)
#define repll(i,a,b) for(ll i=(a);i<=(b);i++)
#define rep(i,n) for(int i=(0);i<(n);i++)
#define repr(i,n) for(int i=(n);i>=0;i--)
#define bs bitset
#define bpc(a) __builtin_popcount(a)
#define tc int t;cin>>t;while(t--)
template<typename T> void TIME(T start, T end)
{
#ifndef ONLINE_JUDGE
    double time_taken =  chrono::duration_cast<chrono::nanoseconds>(end - start).count();
    time_taken *= 1e-9;
    cout << "\nExecuted in: " << fixed
         << time_taken << setprecision(9);
    cout << " sec";
#endif
}

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

ll max(ll a,ll b)
{
    if(a>b)return a;return b;
}
ll min(ll a,ll b)
{
    if(a<b)return a;return b;
}

ll mypow(ll a, ll b) {
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
ll gcd(ll a,ll b)
{
    if(b==0)
    return a;
    return gcd(b,a%b);
}
//..............................!!!!!!Get ready to fight!!!!!!............................


int main()
{   
     auto start = chrono::high_resolution_clock::now();
    fast
    ll n;
    cin>>n;
    vll vec(n);
    ll sum=0;
    rep(i,n){
        cin>>vec[i];
        sum=sum^vec[i];
    }
    vll res(n);
    rep(i,n){
        res[i]=sum^vec[i];
    }
    for(auto it:res){
        cout<<it<<" ";
    }
    auto end = chrono::high_resolution_clock::now();
    TIME(start, end);
    return 0;
}

Measured memory_bytes: 6360
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    ごちゃごちゃ場合分けを考える前に全探索は考えましたか？
*/

int main(){
    int N; cin >> N;
    ll sumA = 0, sumR = 0;
    vector<ll> a(N);
    for(int i=0; i<N; ++i) { cin >> a[i]; sumA += a[i]; }
    sumR = sumA;

    ll tmp = 0;
    queue<ll> q;
    for(int i=1; i<=N-2; i+=2) { tmp += 2*a[i]; q.push(2*a[i]); }
    vector<ll> r(N);

    int id = 2;
    int id2 = 0;
    r[0] = sumR - tmp;

    //cout << sumR << endl << tmp << endl;

    while(id != 0){
        tmp -= q.front();
        q.pop();
        tmp += 2*a[id2];
        q.push(2*a[id2]);
        id2 = (id2+2)%N;
        r[id] = sumR - tmp;
        id = (id+2)%N;
    }

    for(int i=0; i<N; ++i){
        if(i) cout << " ";
        cout << r[i];
    }
    cout << endl;
}

Measured memory_bytes: 3328
#include<stdio.h>

int n,cnt=0;

void print_array(long long elements[]){
    int j;
    for(j=0;j<n;j++){
        printf("%lld",elements[j]);
        if(j<(n-1)) printf(" ");
    }
    printf("\n");
}

void selection_sort(long long elements[]){
    int i,j,mini;
    long long key;

    for(i=0;i<n;i++){
        mini=i;
        for(j=i;j<n;j++){
            if(elements[j]<elements[mini]){
                mini = j;
            }
        }
        if(mini!=i){
            key = elements[i];
            elements[i] = elements[mini];
            elements[mini] = key;
            cnt++;
        }
    }
}

int main(){
    long long elements[100];
    int i;

    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%lld",&elements[i]);
    }

    selection_sort(elements);
    print_array(elements);
    printf("%d\n",cnt);

    return 0;
}

Measured memory_bytes: 604
using System;

namespace ConsoleApplication3
{
    class Program
    {
        static void Main(string[] args)
        {
            int num = int.Parse(Console.ReadLine());
            bool[,] dimArray = new bool[4, 14];

            for (int i = 0; i < num; i++)
            {
                string[] card = Console.ReadLine().Split(' ');
                switch (card[0])
                {
                    case "S":
                        dimArray[0, int.Parse(card[1])] = true;
                        break;
                    case "H":
                        dimArray[1, int.Parse(card[1])] = true;
                        break;
                    case "C":
                        dimArray[2, int.Parse(card[1])] = true;
                        break;
                    case "D":
                        dimArray[3, int.Parse(card[1])] = true;
                        break;
                }
            }

            for (int i = 0; i < 4; i++)
            {
                for (int j = 1; j < 14; j++)
                {
                    if (!dimArray[i, j])
                    {
                        switch(i)
                        {
                            case 0:
                                Console.WriteLine("S" + " " + j);
                                break;
                            case 1:
                                Console.WriteLine("H" + " " + j);
                                break;
                            case 2:
                                Console.WriteLine("C" + " " + j);
                                break;
                            case 3:
                                Console.WriteLine("D" + " " + j);
                                break;
                        }
                    }
                }
            }
        }
    }
}

Measured memory_bytes: 9152
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = pow(10, 9) + 7;
//const int MOD = 998244353;
//const int MOD = ;
int mod(int A, int M) {return (A % M + M) % M;}
const int INF = 1LL << 60;
const string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string abc = "abcdefghijklmnopqrstuvwxyz";
template <class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template <class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
int divCeil(int A, int B) {return (A + (B - 1)) / B;}

int myGCD(int A, int B)
{
  int a = A, b = B;
  while (a * b != 0  &&  a != 1  &&  b != 1)
  {
    if (a < b) b %= a;
    else a %= b;
  }
  if (a * b == 0) return max(a, b);
  else return 1;
}

signed main()
{
  int N, K;
  cin >> N >> K;

  bool toobig = true;
  int g = 0;
  for (int i = 0; i < N; i++)
  {
    int a;
    cin >> a;
    g = myGCD(g, a);
    if (a >= K) toobig = false;
  }
  
  string ans = "IMPOSSIBLE";
  if (!toobig && K % g == 0) ans = "POSSIBLE";

  cout << ans << endl;
}

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

#define int long long
#define pb push_back
#define mp make_pair
#define f(i,a,n) for(int i=a ; i<n ; i++)
#define all(c) (c).begin(),(c).end()
#define F first
#define S second
#define fast ios:: sync_with_stdio(false),cin.tie(nullptr);
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef vector<pii> vpi;

const int inf = 1e9;
const int inf64 = 1e18;
const int MOD = inf + 7;
const ld PI = acos(-1.0);

int32_t main()
{
	fast;
	int a,b;
	cin >> a >> b;
	cout << a*b - a - b + 1;
	
}



Measured memory_bytes: 256
x1, y1, x2, y2 = gets.split.map(&:to_i)

# x1, y1, x2, y2 = [0, 0, 0, 1]
# x1, y1, x2, y2 = [2, 3, 6, 6]
# x1, y1, x2, y2 = [31, -41, -59, 26]

dx = x2 - x1
dy = y2 - y1

rdx = -dy
rdy = dx

x4 = x1 + rdx
y4 = y1 + rdy
x3 = x2 + rdx
y3 = y2 + rdy

puts [x3, y3, x4, y4].join(" ")


Measured memory_bytes: 1788
#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> a, b;

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

    int M = N;

    while (M) {
        int mi = -1;
        int mv = 0;
        for (int i=0; i < N; ++i) {
            if (i+1 == b[i] && b[i] > mv && b[i] <= M) {
                mv = b[i];
                mi = i;
            }
        }

//        cout << M << " " << mi << " " << b[mi] << endl;
        if (mi >= 0) {
            a.push_back(b[mi]);
            b.erase(b.begin() + mi);
        } else {
            break;
        }
        --M;
    }
    
    if (a.size() != N) cout << -1 << endl;
    else {
        for (int i=N-1; i>=0; --i)
            cout << a[i] << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define MOD                 1000000007LL
#define EPS                 1e-9
#define io                  ios_base::sync_with_stdio(false);cin.tie(NULL);

const int MAXN = 1e5+5;

int main(){
	io;
	int a, b;
	cin >> a >> b;
	int mean = ceil(((double)a+b)/2);
	cout << mean << endl;
	return 0;
}

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

int main(){
    int n, ans;
    cin >> n;
    vector <int> p;
    for(int i=0;i<n;i++){
        int a;
        cin >> a;
        p.push_back(a); 
    }

    sort(p.begin(), p.end(), greater<int>());

    ans = p[0] / 2;
    for(int i=1;i<n;i++){
        ans += p[i];
    }
    
    cout << ans << endl;

    return 0;
}

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

char n[5];

int main(){
  cin >> n;
  if(n[0]==n[1] && n[1]==n[2])
    cout << "Yes" << endl;
  else if(n[1]==n[2] && n[2]==n[3])
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

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

int main() {
  int64_t A, B, C, D;
  cin >> A >> B >> C >> D;
  int64_t E = C * D / __gcd(C, D);
  int64_t ans = B - A + 1 - ((B / C + B / D - B / E) - ((A - 1) / C + (A - 1) / D - (A - 1) / E));
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define MOD 1000000007
using namespace std;
vector<int> num;
int dp[20000][200][3];
int g;
string s;
int getsum(int id,int sum,int tight)
{
    if(id==num.size())
    {
        if(sum%g==0)
            return 1;
        else return 0;
    }
    if(dp[id][sum][tight]!=-1&&tight!=0)
        return dp[id][sum][tight];
    int res=0;
    int k;
    if(tight==0)
        k=num[id];
    else
        k=9;
    for(int i=0;i<=k;i++)
    {
         int newtight=tight;
        if(tight==0&&i<k)
            newtight=1;
        res=(res+getsum(id+1,(i+sum)%g,newtight))%MOD;
    }
    if(tight!=0)
        dp[id][sum][tight]=res;
    return (res+MOD)%MOD;
}
int solve(string s)
{
    num.clear();
    for(int i=0;i<s.size();i++)
        num.push_back(s[i]-48);
    memset(dp,-1,sizeof(dp));
    return getsum(0,0,0);
}
void nhap()
{
    cin>>s;
    cin>>g;
    cout<<((solve(s)-1)+MOD)%MOD<<'\n';
}
 main()
{
    nhap();
}


Measured memory_bytes: 95232
x[8],d;main(i){float e[2],a[]={1.1,0.6,0.2,-1};while(~scanf("%f%f",&e[0],&e[1]))for(i=0;i<2;i++)for(d=0;d<8;d+=2)if(e[i]>=a[d/2])x[d+i]++,d=9; for(i=0;i<8;i+=2)printf("%d %d\n",x[i],x[i+1]);exit(0);}

Measured memory_bytes: 0
N = int(input())
A = list(map(int,input().split()))
ans = [float('inf')]*N
ans[0] = 0
ans[1] = abs(A[0]-A[1])
for i in range(2,N):
  ans[i] = min(ans[i-1]+abs(A[i]-A[i-1]), ans[i-2]+abs(A[i]-A[i-2]))
print(ans[N-1])

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

#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = (n)-1; i >= 0; i--)
#define rep1(i,n) for(int i = 1; i <= (n); i++)
#define rrep1(i,n) for(int i = (n); i > 0; i--)

#define ll long long
#define pi pair<int, int>
#define pll pair<ll, ll>

#define MOD 1000000007
#define INF 1000000000000000LL

using namespace std;

int main(){
  int n,p;cin>>n>>p;
  string s;cin>>s;

  vector<ll>edited_nums(n), cum_nums(n);
  int ten=1;
  rrep(i, n){
    int c = s[i]-'0';
    edited_nums[i]=ten*c%p;
    ten = ten*10%p;
  }
  cum_nums[n-1] = edited_nums[n-1];
  for(int i=n-2; i>=0;i--){
    cum_nums[i]=(edited_nums[i]+cum_nums[i+1])%p;
  }

  if(p==2 || p==5){
    ll result = 0;
    rep(i, n)if((s[i]-'0')%p==0)result += (i+1);
    cout<<result;
    return 0;
  }

  ll result = 0;
  map<ll,ll>cnt;
  cnt[0]=1;
  rrep(i, n){
    ll ci = cum_nums[i];
    result+=cnt[ci];
    cnt[ci]++;
  }

  cout<<result<<endl;

//  rrep(i, n)cout<<cum_nums[i]<<' ';cout<<endl;
//  rrep(i, n)cout<<edited_nums[i]<<' ';cout<<endl;

  return 0;
}


Measured memory_bytes: 4100
#include<stdio.h>
int main(void){
    int i,j,l,n,m,y=0,z,k;
    int c[1100]={0},t[1100]={0},cnt[1100]={0},flag[1100]={0},x;
    scanf("%d %d",&n,&m);
    for(i=0;i<n;i++){
        scanf("%d",&c[i]);
    }
    for(j=0;j<m;j++){
    scanf("%d",&t[j]);
    }
    for(i=0;i<n;i++){
        for(j=0;j<m;j++){
        x=c[i]-t[j];
        if(flag[j]==0){
        if(x<=0){
           cnt[i]++;
           flag[j]=1;
         }
        }
       }
       for(k=0;k<i;k++){
            if(k==0)z=cnt[i];
            if(z<=cnt[k]){
                z=cnt[k];
                y=k;
            }
            //else 
            //printf("%d %d %d %d\n",cnt[i],cnt[k],z,y);
          }
        }
    //printf("%d %d %d %d %d\n",c[i],x,flag[j],cnt[i]);
    printf("%d\n",y+1);
return 0;
}

Measured memory_bytes: 1040
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<vector>
typedef long long int ll;
#define REP(i, n) for(int i = 0; i < (n); i++)
#define FOR_IN(i, a, b) for(int i = (a); i < (b); i++)
#define BETWEEN(x, a, b) ((x) >= (a) && (x) <= (b))
#define BIT(b, i) (((b) >> (i)) & 1)
#define LOG_F 1
#define LOG(...) if(LOG_F) fprintf(stderr, __VA_ARGS__)

using namespace std;

ll pow(int x, int n){
  return n == 0 ? 1 : x * pow(x, n - 1);
}

void Yn(bool f)
{
  cout << (f ? "Yes" : "No") << endl;
}

void yn(bool f)
{
  cout << (f ? "yes" : "no") << endl;
}

void YN(bool f)
{
  cout << (f ? "YES" : "NO") << endl;
}


int h, w,f[1001][1001];
int di[] = {1, 0, -1, 0};
int dj[] = {0, 1, 0, -1};
typedef pair<int, int> P;

int main()
{
  cin >> h >> w;
  queue<P> q;
  REP(i, h)
  {
    REP(j, w){
      char c;
      cin >> c;
      if(c == '.'){
        f[i][j] = -1;
      } else {
        f[i][j] = 0;
        q.push(P(i, j));
      }
    }
  }

  int k;
  while (!q.empty())
  {
    P p = q.front();
    q.pop();
    int i = p.first;
    int j = p.second;
    k = f[i][j];

    for (int s = 0; s < 4; s++)
    {
      if (!BETWEEN(i + di[s], 0, h - 1) || !BETWEEN(j + dj[s], 0, w - 1))
        continue;
      int a = f[i + di[s]][j + dj[s]];
      if (a < 0)
      {
        f[i + di[s]][j + dj[s]] = k + 1;
        q.push(P(i + di[s], j + dj[s]));
      }
    }
 
  }
  cout << k << endl;
  return 0;
}


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

using namespace std;
using ll=long long;
using vi=vector<int>;

int main() {
    ios::sync_with_stdio (false), cin.tie (0);
    int n;
    cin >> n;
    vi a(n);
    for(int & i : a)
        cin >> i;
    ll ans = 0;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
          ans += a[i] * a[j];
        }
    }
    cout << ans << '\n';



    return 0;
}













Measured memory_bytes: 256
#include <bits/stdc++.h>
#define debug(...)
#include <complex.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;


int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n , x;
    cin >> n >> x;
    vi a(n);
    for(int & i : a)
        cin >> i;
    sort(a.begin() , a.end());
    int ans = 0;
    for(int i = 0; i < n; i++){
        if( i + 1 < n&& a[i] < x){
            ans++;
            x -= a[i];
        }
        else if(a[i] == x){
            ans++;
            x = 0;
            break;
        }
    }
    cout << ans << '\n';



    return 0;
}














Measured memory_bytes: 256
//#include <algorithm>
#include <iostream>
#include <list>
#include <map> //連想配列
#include <queue>
#include <set>
#include <stack>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector> //動的配列

#define rep(i, N) for (int i = 0; i < N; i++)
#define ll long long
using namespace std;

int main()
{
ll N,M;
cin >> N >> M ;

ll H[N+1];
ll H_flag[N+1];
rep(i,N+1){
    H_flag[i] = 1;
}
H_flag[0] = 0;

H[0] = 0;
rep(i,N){
    cin >> H[i+1] ;
}

ll first,second;
rep(i,M){
    cin >> first >> second;
    if (H[first]==H[second]){
        H_flag[first] = 0;
        H_flag[second] = 0;
    }
    else if(H[first]<H[second]){
        H_flag[first] = 0;
    }
    else if(H[first]>H[second]){
        H_flag[second] = 0;
    }
}
int result = 0;
for (int i=1;i<N+1;i++){
    if(H_flag[i]!=0){
        result++;
    }
}
cout << result << endl;
  return 0;
}


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

using namespace std;


//#define REP(i,n)	for(int i=0;i<(n);++i)
#define REP(i,n)	for(int i=0, i##_len=(n); i<i##_len; ++i)


#define INF 		2000000007
#define MOD			998244353

#define MAX 		100005

typedef unsigned int 			uint;
typedef unsigned long long int	ull;
typedef long long int 			ll;

double DP[MAX];

int main(){
	int N,K;cin >> N >> K;
	double P = 0.0;

	REP(i,MAX)DP[i]=1;
	DP[0] = 0;
	for(int i = K-1;i > 0;--i){
		int j = (i*2 > K ? K : i*2);
//		cout << j << endl;
		DP[i] = DP[j]/2;
//		cout << i << ":" << DP[i] << endl;
	}

	REP(i,N){
//		cout << DP[i+1] << endl;
		P += (double)DP[i+1]/N;
	}

//	cout << P << endl;
	printf("%.16f\n",P);

	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
#define dame(a) {out(a);return 0;}
#define decimal cout<<fixed<<setprecision(15);
#define dupli(a) a.erase(unique(all(a)),a.end())
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef tuple<ll,ll,ll,ll> PPP;
typedef multiset<ll> S;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vvvvi=vector<vvvi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vb=vector<bool>;
using vvb=vector<vb>;
const ll inf=1001001001001001001;
const ll INF=1001001001;
const ll mod=1000000007;
const long double eps=1e-60;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void noyes(T b){if(b)out("no");else out("yes");}
template<class T> void NoYes(T b){if(b)out("No");else out("Yes");}
template<class T> void NOYES(T b){if(b)out("NO");else out("YES");}
void outs(ll a,ll b){if(a>=inf-100)out(b);else out(a);}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll modpow(ll a,ll b){a%=mod;if(b==0)return 1;if(b&1)return a*modpow(a,b-1)%mod;ll k=modpow(a,b/2);return k*k%mod;}
ll ans=0,l;
vector<char> id;
ll lastbit(ll i){
    return i&~(i-1);
}
vvi g;
void make(string s){
    int now=0;
    ll ma=inf;
    rep(i,s.size()){
        bool update=false;
        for(ll x:g[now]){
            if(id[x]==s[i]){
                update=true;
                now=x;
            }
        }
        if(!update){
            chmin(ma,i);
            g[now].pb(id.size());
            now=id.size();
            id.pb(s[i]);
            ans^=lastbit(l-i);
        }
    }
}
int main(){
    id.pb('2');
    ll n;cin>>n>>l;
    g=vvi(100005);
    rep(i,n){
        string s;cin>>s;
        make(s);
    }
    if(ans)out("Alice");
    else out("Bob");
}

Measured memory_bytes: 6016
#include<iostream>
#include<queue>
using namespace std;
int main()
{
	long long int n, m, a;
	priority_queue<int>q;    //优先队列自动从大到小排序
	while(cin >> n >> m)
	{
		long long int sum = 0;
		for(long long int i = 0; i < n; i++)
		{
			cin >> a;
			q.push(a);
		}
		for(long long int i = 0; i < m; i++)
		{
			a = q.top() / 2;
			q.pop();
			q.push(a);
		}
		while(!q.empty())
		{
			sum += q.top();
			q.pop();
		}
		cout << sum << endl;
	}
	return 0;
}

Measured memory_bytes: 892
import java.util.*;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    
    if((a*b)%2 == 0){
      System.out.println("Even");
    } else {
      System.out.println("Odd");
    }
  }
}

Measured memory_bytes: 21716
#include<stdio.h>
int main(){
int k=0,z=1,j,i,n,a,b,c,d,e[110],f[110],x=0;
scanf("%d\n",&n);
f[0]=-1;
for(i=0;i<=n;i++){
e[i]=0;
}
for(i=0;i<n*(n-1)/2;i++){
scanf("%d %d %d %d\n",&a,&b,&c,&d);
if(c<d){
e[b]=e[b]+3;
}
else if(c>d){
e[a]=e[a]+3;
}
else{
e[a]++,e[b]++;
}
}
for(i=1000;i>=0;i--){
for(j=1;j<=n;j++){
if(i==e[j]){
f[j]=z;
x++;
k=1;
}
}
if(k==1){
z=z+x;
}
k=0,x=0;
}
for(i=1;i<=n;i++){
printf("%d\n",f[i]);
}
return 0;
}


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

// definition {{{ 1

// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)

#define Scll(x) scanf("%llu", &x)
#define Scll2(x,y) scanf("%llu%llu", &x, &y)
#define Scll3(x,y,z) scanf("%llu%llu%llu", &x, &y, &z)

#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2

// constants {{{ 2
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
// }}} 2

// systems {{{ 2
#define Rep(x,y) for(int x = 0; x < y; x++)
#define Repe(x,y,z) for(int x = z; x < y; x++)
// }}} 2

// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n");
// }}} 2

// }}} 1

int main() {

    char s[300000] = {} ,t[300000] = {};

    Scs(s);
    Scs(t);

    bool alf[127][127] = {{}};

    bool ans = 1;
    Rep( i,200000 ){
        for( int j = 'a'; j < 'z' + 1; j++){
            if( alf[s[i]][t[i]] ) continue;
            if( alf[s[i]][j] ){
                ans = false;
            }
            if( alf[j][t[i]] ){
                ans = false;
            }
        }
        alf[s[i]][t[i]] = true;
    }

    YesNo(ans);

    return 0;
}



Measured memory_bytes: 896
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <climits>
#include <cmath>
#include <vector>
#include <string>

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

#define INF 100000000

using namespace std;

int N, M, R;
int r[8];
int cost[201][201];

//void dijkstra(int u)
//{
//    fill(d, d+N+1, INF);
//    d[u] = 0;
//    bool used[201];
//    fill(used, used+N+1, false);
//
//    while(true) {
//        int v = -1;
//        FOR (i, 1, N+1) {
//            if (!used[i] && (v==-1 || d[i]<d[v]))
//                v = i;
//        }
//        if (v==-1)
//            break;
//
//        used[v] = true;
//
//        FOR(i, 1, N+1) {
//            d[i] = min(d[i], d[v]+cost[v][i]);
//        }
//    }
//}

int d[201][201];
void warshall_floyd()
{
    REP(k, N+1) {
        REP(i, N+1) {
            REP(j, N+1)
                d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
        }
    }
}

int min_cost = INF;
bool used[8];

void dfs(int u, int pos, int cost)
{
    if (pos!=R) {
        REP(i, R) {
            if (!used[i]) {
                used[i] = true;
                dfs(i, pos+1, cost+d[r[u]][r[i]]);
                used[i] = false;
            }
        }
    } else {
        min_cost = min(cost, min_cost);
    }
}


int main()
{
    int A, B, C;
    scanf("%d %d %d", &N, &M, &R);
    REP(i, R)
        scanf("%d ", &r[i]);
    REP(i, N+1) {
        REP(j, N+1) {
            d[i][j] = INF;
            d[j][i] = INF;
        }
    }
    REP(i, M) {
        scanf("%d %d %d", &A, &B, &C);
        d[A][B] = C;
        d[B][A] = C;
    }
    REP(i, N+1)
        d[i][i] = 0;
    warshall_floyd();
    
    REP(i, R) {
        used[i] = true;
        dfs(i, 1, 0);
        used[i] = false;
    }

    cout << min_cost << endl;

    return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    double a[n];
    pair<int,int>p[n];
    int fac[20][20]={};
    for(int i=0;i<n;i++){
        cin>>a[i];
        long long x=(a[i]+0.0000000001)*1000000000;
        int two=0,five=0;
        while(x%2==0)two++,x/=2;
        while(x%5==0)five++,x/=5;
        two=min(18,two),five=min(18,five);
        fac[two+1][five+1]++;
        p[i]={18-two,18-five};
    }
    for(int i=0;i<20;i++)for(int j=0;j<19;j++)fac[i][j+1]+=fac[i][j];
    for(int i=0;i<20;i++)for(int j=0;j<19;j++)fac[j+1][i]+=fac[j][i];
    long long ans=0;
    for(int i=0;i<n;i++){
        int x=fac[19][19]-fac[p[i].first][19]-fac[19][p[i].second]+fac[p[i].first][p[i].second];
        if(p[i].first<10 && p[i].second<10)x--;
        ans+=x;
}
    cout<<ans/2<<endl;
    return 0;
}

Measured memory_bytes: 6832
int main(){
  
  int a, b, c;
  int ans = 0;
  
  scanf("%d%d%d", &a, &b, &c);


  for(int cnt = b; cnt > 0; ){
    if(cnt >= a){
      cnt = cnt - a;
    }else{
      break;
    }
    if(ans >= c){
      break;
    }
    ans++;
  }

  printf("%d\n",  ans);
  
}


Measured memory_bytes: 128
def solve(n, m):
    ans = [-1] * n
    for _ in range(m):
        s, c = input().split()
        s = int(s) - 1
        if ans[s] == c:
            continue
        elif ans[s] == -1:
            ans[s] = c
        else:
            return -1

    if ans[0] == '0':
        if n == 1:
            return '0'
        else:
            return -1
    elif ans[0] == -1:
        if n == 1:
            return '0'
        else:
            ans[0] = '1'
    for i in range(1, n):
        if ans[i] == -1:
            ans[i] = '0'
    return ''.join(ans)


n, m = list(map(int, input().split()))
print(solve(n, m))

Measured memory_bytes: 3064
#include <cstring>
#include <iostream>
using namespace std;
long long Cou[202000];
long long Num[202000];
long long Cal[202000];
long long book[202000];
void cal() {
    Cal[1] = 0;
    Cal[2] = 1;
    for (long long i = 3; i <= 202000; i++) {
        Cal[i] = Cal[i - 1] + i - 1;
    }
    return;
}
int main() {
    long long N;
    cal();
    while (cin >> N) {
        memset(Cou, 0, sizeof(Cou));
        memset(book, 0, sizeof(book));
        for (long long i = 1; i <= N; i++) {
            cin >> Num[i];
            Cou[Num[i]]++;
        }
        long long tempAns = 0;
        for (long long i = 1; i <= N; i++) {
            if (book[Num[i]] == 0) {
                tempAns += Cal[Cou[Num[i]]];
                book[Num[i]]++;
            }
        }
        // cout << "#" << tempAns << endl;
        for (long long i = 1; i <= N; i++) {
            cout << tempAns - Cal[Cou[Num[i]]] + Cal[Cou[Num[i]] - 1] << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 8960
#include <stdio.h>

int partition(int *A ,int p ,int r){
  int x = A[r];
  int i = p-1;
  int tmp;
  for(int j=0;j<r;j++){
    if(A[j] <= x){
      i++;
      tmp = A[i];
      A[i] = A[j];
      A[j] = tmp;
    }
  }
  tmp = A[i+1];
  A[i+1] = A[r];
  A[r] = tmp;
  return i+1;
}

int main(){
  int n,q;
  int A[100000];

  while(scanf("%d",&n) != EOF){
    char c = ' ';
    for(int i=0;i<n;i++){
      scanf("%d",&A[i]);
    }
    q = partition(A,0,n-1);
    for(int i=0;i<n;i++){
      if(i == n-1)
        c = '\n';
      if(i == q)
        printf("[%d]%c",A[i],c);
      else
        printf("%d%c",A[i],c);
    }
  }
  return 0;
}




Measured memory_bytes: 2960
#include <cstdio>
#include <cmath>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

#ifdef _DEBUG
#define DMP(x) cerr << #x << ": " << x << "\n"
#else
#define DMP(x) ((void)0)
#endif

const int MOD = 1000000007, INF = 1111111111; 
using namespace std;
typedef long long lint;

#define int lint

class UnionFind {
private:
	vector<int> data;
	int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }

public:
	UnionFind(int size) : data(size, -1) { }
	bool is_same(int x, int y) { return root(x) == root(y); }
	int size(int x) { return -data[root(x)]; }

	void unify(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;
		}
	}
};

signed main() {

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

	int N, M;
	cin >> N >> M;
	
	vector<pair<int, int>> bridge(M);
	for (int i = 0; i < M; i++) cin >> bridge[i].first >> bridge[i].second;

	vector<lint> ans(M);
	lint unconf = N * (N - 1) / 2, tmp;
	UnionFind land(N);
	for (int i = M - 1; i >= 0; i--) {

		ans[i] = unconf;
		tmp = land.size(bridge[i].first - 1) * land.size(bridge[i].second - 1);
		land.unify(bridge[i].first - 1, bridge[i].second - 1);
		
		// unify前後で島の大きさが変化していなかったら既に同根である島をつないだだけなので引かない
		unconf -= tmp == land.size(bridge[i].first - 1) * land.size(bridge[i].second - 1) ? 0 : tmp;

	}

	for (const auto &elem : ans) cout << elem << "\n";

	return 0;
}

Measured memory_bytes: 4480
//
//  main.cpp
//

#include <algorithm>
#include <array>
#include <assert.h>
#include <iomanip>
#include <iostream>
#include <limits>
#include <math.h>
#include <memory>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

using ll = int64_t;
using ull = uint64_t;

template<typename T>
vector<T> make_vec_nd(T init, size_t size) {
    return vector<T>(size, init);
}
template<typename T, typename... Args>
auto make_vec_nd(T init, size_t size, Args... rest) {
    auto inner = make_vec_nd(init, rest...);
    return vector<decltype(inner)>(size, inner);
}

#define rep(i,a,b) for(ll i=(a);i<(b);i++)
#define rrep(i,a,b) for(ll i=(a)-1;i>=(b);i--)

int main() {
    ll M, K;
    cin >> M >> K;
    if (M == 1) {
        if (K == 0) {
            cout << "0 0 1 1" << endl;
        } else {
            cout << -1 << endl;
        }
    } else if (!(K < (1 << M))) {
        cout << -1 << endl;
    } else {
        rep(n,0,1<<M) {
            if (n != K) {
                cout << n << " ";
            }
        }
        cout << K << " ";
        rrep(n,1<<M,0) {
            if (n != K) {
                cout << n << " ";
            }
        }
        cout << K << endl;
    }
}



Measured memory_bytes: 1792
n,c=map(int,input().split())
d=[list(map(int,(input().split()))) for _ in range(c)]
s=[list(map(int,input().split())) for _ in range(n)]
mod_0,mod_1,mod_2={},{},{}
for i in range(n):
    for j in range(n):
        if (i+j)%3==0:
            mod_2.setdefault(s[i][j]-1,0)
            mod_2[s[i][j]-1]+=1
        elif (i+j)%3==1:
            mod_0.setdefault(s[i][j]-1,0)
            mod_0[s[i][j]-1]+=1
        else:
            mod_1.setdefault(s[i][j]-1,0)
            mod_1[s[i][j]-1]+=1
cost0=[0 for _ in range(c)]
cost1=[0 for _ in range(c)]
cost2=[0 for _ in range(c)]
for i in range(c):
    for j in mod_0.keys():
        cost0[i]+=d[j][i]*mod_0[j]
for i in range(c):
    for k in mod_1.keys():
        cost1[i]+=d[k][i]*mod_1[k]
for i in range(c):
    for l in mod_2.keys():
        cost2[i]+=d[l][i]*mod_2[l]
ans=float('inf')
for i in range(c):
    for j in range(c):
        if i==j:
            continue
        for k in range(c):
            if j==k or i==k:
                continue
            else:
                ans=min(ans,cost0[i]+cost1[j]+cost2[k])
print(ans)

Measured memory_bytes: 5620
N = int(input())
s = ["" for _ in range(N)]
for i in range(N):
    s[i] = input()
M = int(input())
t = ["" for _ in range(M)]
for i in range(M):
    t[i] = input()

s_set = list(set(s))
t_set = list(set(t))

ans = ""
INF = -float("inf")

for i in s_set:
    score = s.count(i) - t.count(i)
    if INF < score:
        INF = score
        ans = i
for i in t_set:
    score = s.count(i) - t.count(i)
    if INF < score:
        INF = score
        ans = i

if INF < 0:
    print(0)
else:
    print(INF)


Measured memory_bytes: 62736
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pp pair<pair<ll, ll>,pair<ll, ll>>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define vii vector<int>
#define vll vector<ll>
#define mat vector<vector<ll>>
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define fi first
#define sc second
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define sz(x) (ll) (x).size()
#define pq priority_queue<ll>
#define pqg priority_queue<ll,vector<ll>,greater<ll>>
#define LB(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define UB(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
#define ERASE(v) sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end())
#define int ll
// #define ll int
using namespace std;
const ll INF = (1 << 30 ) - 1;
const ll LLINF = (1LL << 60LL);
const ll MOD = 1000000007;
const ll mod = 998244353;
const ll MAX = 1100000;
const double pi = acos(-1);
const double eps = 1e-10;
ll dx[8] ={1,0,-1,0,1,-1,1,-1};
ll dy[8] ={0,1,0,-1,1,-1,-1,1};
 
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; }
 
struct Timer{
    chrono::system_clock::time_point start, end;
    Timer(){ start = chrono::system_clock::now(); }
    ~Timer(){
        end = chrono::system_clock::now();
        auto msec = chrono::duration_cast<chrono::milliseconds>(end - start).count();
        cerr<<"time : "<<msec<<" ms"<<endl;
    }
};


void solve(){
    ll n;
    ll a[100010];
    cin>>n;
    rep(i,n) cin>>a[i];
    ll ans=0;
    rep(i,n){
        if(i%2==0&&a[i]%2==1) ans++;
    }
    cout<<ans<<endl;



}


signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    // Timer TM;
     
    solve(); 


    return 0;
}


Measured memory_bytes: 3656
import sys
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
List = [a,b,c,d,e]
k = int(input())
flag = 0
for i in range(5):
    for j in range(5):
        if i == k:
            tmp = 0
        elif abs(List[i]-List[j])>k:
            print(':(')
            sys.exit()
           
print('Yay!')

Measured memory_bytes: 3064
#include <stdio.h>
 
int main(){
  int n,u,k,i,j,v[1000],x[1000][1000];
  scanf("%d",&n);
  for(i = 0; i < n; i++){
    scanf("%d%d",&u,&k);
    for(j = 0; j < k; j++){
      scanf("%d",&v[i]);
      x[u-1][v[i]-1] = 1;
     }
  }
 
  for(i = 0; i < n; i++){
    for(j = 0; j < n; j++){
      if(j == 0){
    if(x[i][j] != 1) printf("0");
    else printf("1");
      }
      else{
    if(x[i][j] != 1) printf(" 0");
    else printf(" 1");
      }
    }
    printf("\n");
  }
 
  return 0;
}


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

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i)
#define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i)
#define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }

typedef pair<int,int> P;

const int MAXN = 1005;
const int MAXV = MAXN*(MAXN-1)/2;
vector<int> to[MAXV];
int id[MAXN][MAXN];
int toId(int i, int j) {
    if (i > j) swap(i, j);
    return id[i][j];
}

bool visited[MAXV]; // 訪れたかのフラグ
bool calculated[MAXV]; // ループ検出用
int dp[MAXV]; // vからスタートした時の最長経路
int dfs(int v) {
    if (visited[v]) {
        if(!calculated[v]) return -1;
        return dp[v];
    }
    visited[v] = true;
    dp[v] = 1;
    for(int u : to[v]) {
        int res = dfs(u);
        if(res == -1) return -1;
        dp[v] = max(dp[v], dfs(u)+1);
    }
    calculated[v] = true;
    return dp[v];
}


int main() {
    int n; cin >> n;
    vector<vector<int>> a(n, vector<int>(n-1));
    rep(i,n) rep(j,n-1) {
        cin >> a[i][j];
        a[i][j]--;
    }
    int V = 0;
    rep(i, n) rep(j, n) {
        if(i < j) id[i][j] = V++; // 頂点番号を割り当てる.
    }
    rep(i, n) {
        rep(j, n-1) {
            a[i][j] = toId(i, a[i][j]);
        }
        rep(j, n-2) {
            to[a[i][j+1]].push_back(a[i][j]);
        }
    }
    int ans = 0;
    rep(i, V) {
        int res = dfs(i);
        if(res == -1) {
            puts("-1");
            return 0;
        }
        ans = max(ans, res);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 38528
#include<bits/stdc++.h>
using namespace std;
#define rep(x,y,z) for (register int x=y; x<=z; x++)
#define downrep(x,y,z) for (register int x=y; x>=z; x--)
#define ms(x,y,z) memset(x,y,sizeof(z))
#define LL long long
#define repedge(x,y) for (register int x=hed[y]; ~x; x=edge[x].nex)
inline int read(){
	int x=0; int w=0; char ch=0;
	while (ch<'0' || ch>'9') w|=ch=='-',ch=getchar();
	while (ch>='0' && ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return w? -x:x;
}
const int N=200005;
int n,a[N];
char s[N];
LL ans,len;
int kd(char ch){
	return (ch=='B')? 0:1;
}   
int main(){
    scanf("%s",&s); n=strlen(s);
    rep(i,0,n-1) a[i+1]=kd(s[i]);
	rep(i,1,n){
		if (a[i]==0) len+=1ll; 
		if (a[i]==1) ans+=len; 
	}
	printf("%lld\n",ans);
    return 0;
}  


Measured memory_bytes: 1280
#include <stdio.h>

int main(){
	
long long int n;
scanf ("%lld", &n);
long long int sum = 0;
for (long long int i = 1; i <= n; i++){
int check = 0;
	if (i % 3 == 0){
	check = 1;
	}
	if (i % 5 == 0){
	check = 1;
	}
	if (check == 0){
	sum += i;
	}
	
}
printf ("%lld", sum);

	return 0;
}

Measured memory_bytes: 2148
import java.io.*;
import java.lang.reflect.*;
import java.util.*;
import java.util.function.*;

final class Solver {
	static final Solver INSTANCE = new Solver();
	private int N;

	void solve(Supplier<String> sc) {
		N = Integer.parseInt(sc.get());
		int M = Integer.parseInt(sc.get());
		int K = Integer.parseInt(sc.get());
		init();
		int sum = 0;
		for (int i = 0; i <= K; i++) {
			long edge = ncr(N - 1, i); // 色変えポイントどれを選ぶか
			sum = (int) ((sum + (edge * (M * modpow(M - 1, N - 1 - i, MOD) % MOD)) % MOD) % MOD);
		}
		System.out.println(sum);
	}

	long modpow(long a, long n, long mod) {
		long res = 1;
		while (n > 0) {
			if (n % 2 == 1) res = res * a % mod;
			a = a * a % mod;
			n /= 2;
		}
		return res;
	}

	static final int MOD = 998244353;

	long[] factorial;
	long[] facInverse;
	long[] inverse ;

	void init() {
		int MAX = N + 2;
		factorial = new long[MAX];
		facInverse = new long[MAX];
		inverse = new long[MAX];
	    factorial[0] = factorial[1] = 1;
	    facInverse[0] = facInverse[1] = 1;
	    inverse[1] = 1;
	    for (int i = 2; i < MAX; i++) {
	        factorial[i] = factorial[i - 1] * i % MOD;
	        long inv = inverse[i] = MOD - inverse[MOD % i] * (MOD / i) % MOD;
	        facInverse[i] = facInverse[i - 1] * inv % MOD;
	    }
	}

	long ncr(int n, int r) {
	    if (n < r) return 0;
	    if (n < 0 || r < 0) return 0;
	    return factorial[n] * (facInverse[r] * facInverse[n - r] % MOD) % MOD;
	}
}

class Main {
	public static void main(String... args) {
		System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
		var reader = new BufferedReader(new InputStreamReader(System.in));
		Solver.INSTANCE.solve(new Supplier<>() {
			StringTokenizer line;

			public String get() {
				while (line == null || !line.hasMoreTokens()) try {
					line = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new UncheckedIOException(e);
				}
				return line.nextToken();
			}
		});
		System.out.flush();
	}
}

Measured memory_bytes: 37520
import fractions
import sys
import copy
def lcm(x, y):
    return (x*y)//fractions.gcd(x, y)

n,m=map(int,input().split())
a=list(map(int,input().split()))
b=copy.copy(a)
b=list(set(b))
n2=len(b)

count=n2
while count!=0:
  count=0
  for i in range(n2):
    if b[i]%2==0:
      b[i]=b[i]//2
      count+=1
  if len(set(b))!=n2:
    print(0)
    sys.exit()

for i in range(n):
  a[i]=a[i]//2
L=a[0]
for i in range(1,n):
  L=lcm(L,a[i])
  if L>=10**9+1:
    print(0)
    sys.exit()

if (m//L)%2==0:
  print((m//L)//2)
else:
  print(((m//L)//2)+1)

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

const ll MOD = 1e9 + 7;

int main(){
    cin.tie(0)->sync_with_stdio(false);

	int n; cin >> n;
	vector<ll> a(n);
	REP(i, n) cin >> a[i];
	sort(a.begin(), a.end());

	ll cnt = 0;
	if(n % 2) {
		bool ok = true;
		REP(i, n) {
			int tmp = i;
			if (i % 2) tmp++;
			if (tmp != a[i]) {
				ok = false;
				break ;
			}
		}
		if (ok) cnt = n / 2;
	} else {
		bool ok = true;
		REP(i, n) {
			int tmp = i;
			if (!(i % 2)) tmp++;
			if (tmp != a[i]) {
				ok = false;
				break ;
			}
		}
		if (ok) cnt = n / 2;
	}

	if (n == 1 && a[0] == 0) {
		cout << 1 << '\n';
	} else if (cnt) {
		ll ans = 1;
		REP(i, cnt) {
			ans *= 2;
			ans %= MOD;
		}
		cout << ans << '\n';
	} else cout << cnt << '\n';
    return 0;
}


Measured memory_bytes: 3960
#include<bits/stdc++.h>
using namespace std;
vector<int>ad[100009];
int dist[100009];
int visited[100009];
int indegree[100009];

void dijkstra(int s)
{
    visited[s] = 1;
    for(auto x : ad[s])
    {
        dist[x] = max(dist[x] , dist[s]+1);
        indegree[x]--;
        if(indegree[x] == 0)dijkstra(x);
    }


}
int main()
{
    int i,j,k,l,m,n,a,b;
    cin>>n>>m;
    while(m--)
    {
        cin>>a>>b;
        ad[a].push_back(b);
        indegree[b]++;
    }
    for(i=1;i<=n;i++)
    {
        if(indegree[i] == 0 && visited[i]==0)
        {
            dijkstra(i);
        }
    }
    int ans = 0 ;
    for(i=1;i<=n;i++)
    {
        ans = max(ans,dist[i]);
    }

    cout<<ans<<endl;
}


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

const long long MOD = 1000000007;
const int INF = 1<<29;
const double EPS = 1e-8;
typedef vector<int> vec;
typedef pair<int,int> P;
typedef long long ll;

ll dfs(ll X, ll A){
    if(X <= A){
        if(A%X == 0){
            return (2*(A/X) - 1) * X;
        }else{
            return (A/X)*2*X + dfs(X, A % X);
        }
    }else{
        if(X%A == 0){
            return (2*(X/A) - 1) * A;
        }else{
            return (X/A)*2*A + dfs(X % A, A);
        }
    }
}

int main(){
    ll N, X;
    cin >> N >> X;
    cout << N + dfs(X, N-X) << endl;
    return 0;
}


Measured memory_bytes: 256
S = input()
T = input()
m = 0
lt = len(T)
for i in range(len(S)- lt+1):
    pm = 0
    ps = S[i:lt+i]
    for j in range(lt):
          if ps[j] == T[j]:
               pm += 1
    m = max(m,pm)
              #m = max(m,len(T[i:j]))
print(len(T)-m)


Measured memory_bytes: 67800
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <tuple>
#include <set>
#include <assert.h>
#include <sstream>
#include <string>
//#include <bits/stdc++.h>
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i,i0,n) for(int (i)=(i0);(i)<(n);(i)++)
#define FORR(i,i0,n) for(int (i)=(n)-1; (i)>=(i0);(i)--)
#define SORT(x) sort(x.begin(),x.end())
#define SORTR(x) sort(x.begin(),x.end(),greater <>())
#define rn return
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
using namespace std;
using ll = long long;
typedef std::pair<int,int> P;
//#include <boost/multiprecision/cpp_int.hpp>
//using bint = boost::multiprecision::cpp_int;





int main(){
    int INF = 1e9+7;
    int h,n;
    cin >> h >> n;
    vector<int> a(n),b(n);
    rep(i,n) cin >> a[i] >> b[i];
    vector<int> dp(h+1,INF);
    dp[0] = 0;
    rep(i,h){
        rep(j,n){
            int newi = i + a[j];
            newi = min(h,newi);
            dp[newi] = min(dp[newi],dp[i]+b[j]);
        }
    }
    cout << dp[h];
}


Measured memory_bytes: 256