akhauriyash/Code-Regression huggingface dataset:
N, K = map(int, input().split())
A = [[0 for _ in range(N)] for _ in range(30)]
B = [0] * N
for i in range(N):
  a, b = map(int, input().split())
  for j in range(30):
    A[j][i] = a % 2
    a //= 2
  B[i] = b
M = [0] * 30
_M = [0] * N
_K = K
for i in range(30):
  k = _K % 2
  M[i] = k
  _K //= 2
  if k:
    continue
  for j in range(N):
    _M[j] += A[i][j]
cnt = 0
for i in range(N):
  if _M[i]:
    continue
  cnt += B[i]
Z = [0] * N
for i in range(30):
  if M[i] == 0:
    for j in range(N):
      Z[j] += A[i][j]
  else:
    _cnt = 0
    for j in range(N):
      _M[j] += A[i][j] - Z[j]
      Z[j] = A[i][j]
      if _M[j]:
        continue
      _cnt += B[j]
    cnt = max(_cnt, cnt)
print(cnt)

Measured memory_bytes: 118340
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> l_l;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
const int INF=1001001000;
const int mINF=-1001001000;
const ll LINF=1010010010010010000;
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;
}
//グリッド：（典型）dp,dfs,bfs,最短経路,その他
int n,h;
vl a(110000),b(110000);
int main(){
    cin>>n>>h;
    rep(i,n)cin>>a[i]>>b[i];
    ll mx=0;
    int idx=-1;
    rep(i,n){
        if(chmax(mx,a[i])) idx=i;
    }
    vl thr;
    bool duplicate=false;
    rep(i,n){
        if(b[i]>mx){
            if(i==idx) duplicate=true;
            thr.push_back(b[i]);
        }
    }
    ll sum=0;
    sort(thr.rbegin(),thr.rend());
    rep(i,(int)thr.size()){
        sum+=thr[i];
        if(sum>=h){
            cout<<i+1<<endl;
            return 0;
        }
    }
    ll cnt=0;
    cnt+=(int)thr.size();
    if(duplicate) {
        sum-=b[idx];
        ll need=h-sum;
        cnt+=(need-b[idx]+mx-1)/mx;
        cout<<cnt<<endl;
    }
    else{
        ll need=h-sum;
        cnt+=(need+mx-1)/mx;
        cout<<cnt<<endl;
    }
    return 0;
}

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

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using usize = std::size_t;
template<typename T>
using Vector = std::vector<T>;
using String = std::string;
template<typename T>
using UniquePointer = std::unique_ptr<T>;
using namespace std;

#define rep(i, max) for(usize i = 0; i < max; ++i)
#define loop while(true)

UniquePointer<String> readLine() {
    UniquePointer<String> line(new String());
    getline(cin, *line);
    return line;
}

template<typename T1, typename T2>
pair<T1, T2> readPair(){
    T1 res1;
    cin >> res1;
    T2 res2;
    cin >> res2;
    readLine();
    return make_pair(res1, res2);
}

template<typename T>
UniquePointer<Vector<T>> readVector(usize num) {
    UniquePointer<Vector<T>> list(new Vector<T>(num));
    rep(i, num) {
        cin >> (*list)[i];
    }
    readLine();
    return list;
}

void readValues()
{
    readLine();
}

template<typename H, typename... T>
void readValues(H& head, T&&... tails){
    H a;
    cin >> a;
    head = a;
    readValues(forward<T>(tails)...);
}

template<typename T>
void writeLine(T arg) {
    cout << arg << endl;
}

template<typename T>
void write(T arg) {
    cout << arg << std::flush;
}

void program();

int main()
{
    ios::sync_with_stdio(false);
    program();
}

void program() {
    int h, n;
    readValues(h, n);
    auto a = readVector<i32>(n);

    rep(i, n){
        h -= (*a)[i];
        if(h <= 0){
            writeLine("Yes");
            return;
        }
    }
    writeLine("No");
}

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

#define debug(x) cout <<"DEBUG"<<" "<< #x << ":" << x << '\n'

// n回繰り返し
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順
#define rep1(i,n) for(int i = 1; i <= ((int)(n)); i++) // 1-indexed昇順
#define rrep(i,n) for(int i = ((int)(n)-1); i >= 0; i--)  // 0-indexed降順
#define rrep1(i,n) for(int i = ((int)(n)); i >= 1; i--)   // 1-indexed降順
#define all(x) (x).begin(),(x).end()

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vii;  // 2次元配列
typedef vector<ll> vll;
typedef pair<int, int> PII;

template<typename T>
using vec = vector<T>;
template<class T>
using maxheap = std::priority_queue<T>;
template<class T>
using minheap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

template<class T,class U> inline bool chmax(T &a, const U &b){if(a<b){a=b;return 1;}return 0;}
template<class T,class U> inline bool chmin(T &a, const U &b){if(a>b){a=b;return 1;}return 0;}

const ld Pi = std::acos(-1.0L);
const ll infll = (1LL<<62)-1;
const int inf = (1<<30)-1;
const int mod = 1000000007;
// const int mod = 998244353;


/*FUNCs=================================================*/


/*MAIN==================================================*/
signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);   //cin cout 高速化
    cout << fixed << setprecision(15);

    int n,k; cin >> n >> k;
    vec<double> p(n);
    rep(i,n) {
        double pp; cin >> pp;
        p[i] = (1+pp)*pp;
        p[i] /= 2;
        p[i] /= pp;
        // p[i] = (1+pp)/2;
    }
    vec<double> csum(n+1);
    csum[0] = 0;
    rep(i,n) {
        csum[i+1] = csum[i] + p[i];
    }
    double maxi = 0;

    // for(auto c : p) debug(c);
    // for(auto d: csum) debug(d);

    for(int i= 0; i < n-k+1; ++i) {
        double q = csum[i+k] - csum[i];
        // debug(q);
        chmax(maxi, q);
    }
    cout << maxi << '\n';
}

Measured memory_bytes: 3328
#include <iostream>

using namespace std;

int main()
{
    int r,g,b,n;
    int cnt = 0;
    cin >> r >> g >> b >> n;
    if(g > r && g > b){
      int tmp = g;
      g = r;
      r = tmp;
    }
    if(b > g && b > r){
      int tmp = b;
      b = r;
      r = tmp;
    }
    for(int i = 0;i <= n / r; i++){
      for(int j = 0;j <= n / g; j++){
        if(r * i + g * j > n){
          break;
        }
        if((n - (r * i + g * j)) % b == 0){
          cnt++;
        }
      }
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define PI acos(-1)
typedef  long long ll;
ll gcd(ll x,ll y){
   if(y==0) return x;
   else return gcd(y,x%y);
}
ll lcm(ll x,ll y){
   return x/gcd(x,y)*y;
}

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

   long double ans=0;

   for(int i=1;i<=n;i++){
      int x;
      int count=0;
      while(true){
         int a=pow(2,count)*i;
         if(a>=k){
            x=count;
            break;
         }
         count++;
      }

      long double y=(double)pow(2,x);
      y*=n;
      long double z=1/y;
      ans+=z;
      
   }
   cout<<std::setprecision(10)<<ans<<endl;
   
   return 0;
}


Measured memory_bytes: 4080
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define ll long long
using namespace std;
//typedef vector<unsigned int>vec;
//typedef vector<ll>vec;
//typedef vector<vec> mat;
typedef pair<int, int> P;
typedef pair<ll,ll> LP;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int INF = 1000000000;
const ll LINF = 1000000000000000000;//1e18
const ll  MOD = 1000000007;
const double PI = acos(-1.0);
const double EPS = 1e-10;

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; }
template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};



int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll A, B;
    cin >> A >> B;
    for(ll i=1;i<=INF;i++){
        if(abs(A-i) == abs(B-i)){
            cout << i << endl;
            return 0;
        }
    }
    cout << "IMPOSSIBLE" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n; cin >> n;
    int f[50];
    f[0] = 1;
    f[1] = 1;
    for(int i = 2; i < 50; i++) f[i] = f[i-1] + f[i-2];
    cout << f[n] << endl;
    return 0;
}


Measured memory_bytes: 3104
n, m = map(int, input().split())
list_ship = [[] for _ in range(n)]
for _ in range(m):
  a, b = map(int, input().split())
  list_ship[a-1].append(b-1)
  list_ship[b-1].append(a-1)

same_island = set(list_ship[0]) & set(list_ship[-1])
if len(same_island) > 0:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Measured memory_bytes: 48572
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;


class Program
{
    public void Slove()
    {    
        int n = int.Parse(Console.ReadLine());
        int[] ls =
            Console.ReadLine().Split()
            .Select(int.Parse)
            .OrderByDescending(x => x)
            .ToArray();
        bool result = ls.Skip(1).Sum() > ls[0];
        Console.WriteLine(result ? "Yes" : "No");
    }
    static void Main(string[] args)
    {
        var p = new Program();
        p.Slove();
    }
}


Measured memory_bytes: 13396
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,n) for(int i=(a); i<(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(10);

    int L; cin >> L;
    double ans = pow((L/3.0), 3);
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
int main() {
  int n,a[100005]={},b;
  cin >> n;
  for(int i=0; i<n; i++) {
    cin >> b;
    a[b]=i+1;
  }
  for(int i=0; i<n; i++) {
    cout << a[i+1] << " ";
  }
  cout << endl;
}

Measured memory_bytes: 1152
l = [int(input()) for i in range(4)]
c = 0
for i in range(l[0]+1):
        for j in range(l[1]+1):
                for k in range(l[2]+1):
                        now = 500*i + 100*j + 50*k
                        if now == l[3]:
                                c += 1

print(c)

Measured memory_bytes: 3064
#include <vector>
#include <string>
#include <cstdint>
#include <bits/stdc++.h>

using namespace std; //ごめんなさい

vector<int> RH(string S,string T){
  int SN=S.size();
  int TN=T.size();
  int_fast64_t b=9973; 
  vector<int_fast64_t>mod={1000000007LL,1000000009LL,1000000021LL}; 
  int M=mod.size();
  vector<int_fast64_t>s(M,0);
  vector<int_fast64_t>t(M,0);
  vector<int_fast64_t>a(M,1);
  for(int i=0;i<TN;i++){
    for(int j=0;j<M;j++){
      a[j]=(a[j]*b)%mod[j];
    }
  }
  for(int i=0;i<TN;i++){
    for(int j=0;j<M;j++){
      s[j]=((s[j]*b)%mod[j]+S[i])%mod[j];
    }
  }
  for(int i=0;i<TN;i++){
    for(int j=0;j<M;j++){
      t[j]=((t[j]*b)%mod[j]+T[i])%mod[j];
    }
  }
  vector<int>res;
  bool ok=true;
  for(int i=0;i<M;i++)if(s[i]!=t[i])ok=false;
  if(ok)res.push_back(0);
  for(int i=0;i+TN<SN;i++){
    ok=true;
    for(int j=0;j<M;j++){
      s[j]=((s[j]*b)%mod[j]-(S[i]*a[j])%mod[j])%mod[j];
      if(s[j]<0)s[j]+=mod[j];
      s[j]=(s[j]+S[i+TN])%mod[j];
      if(s[j]!=t[j])ok=false;
    }
    if(ok)res.push_back(i+1);
  }
  return res;
}


int main(){
  string S,T;
  cin>>S>>T;
  auto v=RH(S,T);
  for(auto it:v)cout<<it<<endl;
  return 0;
}



Measured memory_bytes: 9436
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>

#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)
#define FOR(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define RREP(i,a) for(int (i)=(a)-1;(i)>=0;(i)--)
#define FORR(i,a,b) for(int (i)=(a)-1;(i)>=(b);(i)--)
#define PI acos(-1.0)
#define DEBUG(C) cout<<C<<endl;
#define VI vector<int>
#define VII vector<VI>
#define VL vector<LL>
#define VLL vector<VL>
#define VD vector<double>
#define VDD vector<VD>
#define PII pair<int,int>
#define PDD pair<double,double>
#define PLL pair<LL,LL>
#define VPII vector<PII>
#define ALL(a) (a).begin(),(a).end()
#define SORT(a) sort(ALL(a))
#define REVERSE(a) reverse(ALL(a))
#define MP make_pair
#define EP emplace_back
#define FORE(a,b) for(auto &&a:b)

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int INF=1e9;
const int MOD=INF+7;

int main(void){
    int N; cin >> N;
    VPII A(N);
    REP(i,N){
        int a; cin >> a;
        A[i]=MP(a,i);
    }
    SORT(A);
    int ans=0;
    REP(i,N){
        if(A[i].second%2!=i%2) ans++;
    }
    if(ans%2) ans=(ans/2)+1;
    else ans/=2;
    cout << ans << endl;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
//#include <atcoder/all>
#define ll long long int
#define vec vector<ll>
#define mat vector<vector<ll>>

using namespace std;
//using namespace atcoder;

const ll mod=1000000007;
const ll inf=LONG_LONG_MAX;
ll dx4[4]={1,0,-1,0};
ll dy4[4]={0,-1,0,1};
ll dx8[8]={1,0,-1,1,-1,1,0,-1};
ll dy8[8]={1,1,1,0,0,-1,-1,-1};

int main(){

  ll n;
  cin >>n ;
  cout << 1-n << endl;

  return 0;
}

Measured memory_bytes: 3588
#include <stdio.h>
#include <stdlib.h>
#define MAX 2000001
#define VMAX 10000

int main(){
  int *A, *B;
  int C[VMAX+1];
  int n, count=0, i, j, k=0;

  scanf("%d", &n);

  A = malloc(sizeof(int)*n+1);
  B = malloc(sizeof(int)*n+1);

  for(i=1;i<n+1;i++){
    scanf("%d",&A[i]);
  }
  for(i=0;i<n+1;i++){
    if(k<A[i])k=A[i];
  }
  
  for(i=0;i<k;i++){
    C[i] = 0;
  }

  for(j=1;j<n+1;j++){
   C[A[j]]++;
  }

   for(i=1;i<VMAX+2;i++){
    C[i] += C[i-1];
  }
  
  for(i=n;i>0;i--){
    B[C[A[i]]] = A[i];
    C[A[i]]--;
  }
  
  
  for(i=1;i<n+1;i++){
    if(i==n)printf("%d\n",B[i]);
    else printf("%d ",B[i]);
  }
  
  
  return 0;
}



Measured memory_bytes: 17524
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
s=SI()
t=SI()
n=len(s)
if t[0:n]==s and len(t)==n+1:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 9416
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i,n) for(int i=0; i < (n); ++i)
#define REPR(i,n) for(int i=(n); i >=0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
 
typedef long long ll;
#define INF 1e9
 
 
int main(){
  int N, K, zero = 1e9;
  cin >> N >> K;
  vector<int> x(N), minus, plus(1,0);
  REP(i, N){
    cin >> x[i];
    if(x[i] > 0){
      plus.push_back(x[i]);
    }
    else if(x[i] < 0){
      minus.push_back(-x[i]);
    }
    else{
      K--;
    }
  }
  minus.push_back(0);
  int ans = 1e9;
  
  for(int i =max((int)(K-minus.size()+1),0); i <= K && i < plus.size(); i++){
    // cout << "minus.size():" << minus.size() << " K:" << K << " i:" << i << endl;
    // cout << minus[minus.size()-1-K+i] << endl;
    ans = min(ans, (2*plus[i]+(minus[minus.size()-1-K+i])));
    ans = min(ans, (plus[i] + 2*(minus[minus.size()-1-K+i])));
  }
  cout << ans << endl;


 
  return 0;
}

Measured memory_bytes: 1404
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>

#define whole(s) (s).begin(), (s).end()
#define putlld(d) printf("%lld\n", (d))

using namespace std;

typedef long long i64;
typedef vector<i64> vx;

int main(void) {
    int N, Q;
    cin >> N >> Q;

    vx b;
    i64 q;
    b.push_back(N);

    int i;
    for (i=0; i<Q; i++) {
        scanf("%lld", &q);
        while (b.size() && b.back()>=q) b.pop_back();
        b.push_back(q);
    }

    vx res(N+1), t(N);
    t[b.size()-1] = 1;
    for (i=b.size(); i--;) {
        i64 k=b[i];
        while (k > b[0]) {
            int j;
            j = lower_bound(whole(b), k) - (b.begin()+1);
            t[j] += k/b[j]*t[i];
            k %= b[j];
        }
        res[k] += t[i];
    }

    for (i=N; --i;) {
        res[i] += res[i+1];
    }

    for (i=1; i<=N; i++) {
        putlld(res[i]);
    }

    return 0;
}


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

int main(){
  int c[3][3];
  for (int i = 0; i < 3; i++) cin >> c[i][0] >> c[i][1] >> c[i][2];

  int a[3], b[3];
  a[0] = 0;
  int count = 0;
  for (int i = 0; i < 3; i++) b[i] = c[0][i];

  for (int i = 1; i < 3; i++) {
    a[i] = c[i][0] - b[0];
  }
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      if (a[i] + b[j] != c[i][j]) count++;
    }
  }

  if (count == 0) cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
using namespace std;
using namespace __gnu_pbds; 
#define     mod             1e9+7
#define     MOD             998244353
#define     ll             long long
#define     mp              make_pair
#define     F               first
#define     S               second
#define     pb              emplace_back
#define     pf              emplace_front
#define     all(p)          p.begin(), p.end()
#define     rep(i,a,b)      for( i=a;i<b;++i)
#define     repr(i,a,b)     for( i=a;i>=b;i--)
#define     up              upper_bound
#define     lb              lower_bound
#define     t()             int test;cin>>test;while(test--)
#define     setbits(x)      __builtin_popcountll(x)
#define     si              set<int>
#define     mii             map<int,int>
#define     vi              vector<int>
#define     ii              pair<int,int>
#define     que_max         priority_queue <int>
#define     que_min         priority_queue <int, vi, greater<int> >
#define     vii             vector<ii>
#define     IOS             ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define     endl            "\n"
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <typename Arg1>
    void __f(const char* name, Arg1&& arg1){
        cout << name << " : " << arg1 << endl;
        //use cerr if u want to display at the bottom
    }
    template <typename Arg1, typename... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args){
        const char* comma = strchr(names + 1, ','); cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
    }
#else
#define trace(...)
#endif


int32_t main()
 
{  
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output 3.txt", "w", stdout);
    #endif

    IOS;
   ll int n,k;
   cin>>n>>k;
   std::vector<int> v(n+1);
  map<int,int> m;
   int i;
   rep(i,1,n+1)
   {
     cin>>v[i];
   }
   std::vector<int> cycle;
   i=1;
   while(1)
   {  
        m[i]++;
        if(m[i]>1)break;
        cycle.pb(i);
        i=v[i];
   }
   int ele;
   for(auto i:m)
   {
     if(i.S>1)
     {
        ele=i.F;
     }
   }
   int ind,rem=0;;
   for(i=0;i<cycle.size();i++)
   {
      if(ele==cycle[i])
      {
        ind=i;
        break;
      }
      rem++;
   }
 
  std::vector<int> a(cycle.begin()+ind,cycle.end());
 
   if(k<rem)
   {
      cout<<cycle[k]<<endl;
      return 0;
   }
   
     int index=(k-ind)%a.size();
   
 
   cout<<a[index]<<endl;

}

Measured memory_bytes: 14064
/*
 _    _    _______   _    _
| |  / /  |  _____| | |  / /
| | / /   | |       | | / /
| |/ /    | |_____  | |/ /
| |\ \    |  _____| | |\ \
| | \ \   | |       | | \ \
| |  \ \  | |_____  | |  \ \
|_|   \_\ |_______| |_|   \_\

*/
/*#include <iostream>
#include <cstdio>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <cstring>
#include <string>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <assert.h>*/

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef double ld;
typedef pair <int, int> PII;
typedef pair <ll, ll> PLL;

#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define right(x) x << 1 | 1
#define left(x) x << 1
#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)
#define mkp make_pair
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define y1 kekekek

const ll ool = 1e18 + 9;
const int oo = 1e9 + 9, base = 1e9 + 7;
const ld eps = 1e-7;
const int N = 2e6 + 6;

string s;
int ans = oo;

int main() {
	ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin >> s;
    int n = sz(s);
    forn(i, 0, sz(s) - 1) {
        int cnt = 0, mx = 0;
        forn(j, 0, n - 1) {
            if (s[j] == s[i]) {
                mx = max(mx, cnt);
                cnt = 0;
            }
            else ++cnt;
        }
        mx = max(mx, cnt);
        ans = min(ans, mx);
    }

    cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#if defined __has_include
# if __has_include(<bits/debug_aamir.h>)
#  define dbg(...) DEBUG(#__VA_ARGS__, __VA_ARGS__);
#  include<bits/debug_aamir.h>
# else
#  define dbg(...)
# endif
#endif

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef long long ll;
typedef pair<ll, ll> pll;
#define sz(x) int(x.size())
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define rep(i, begin, end) for(__typeof(end) i=begin; i<end; i++)
#define per(i, begin, end) for(__typeof(end) i=begin; i>=end; i--)
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
constexpr int INF = 1e9 + 1;
constexpr ll LLINF = 1e18 + 1;


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;		}

ii operator + (ii &a, ii &b){
	return {a.fi+b.fi, a.se+b.se};
}

int main()
{
	fastio;
	string s, t;
	cin >> s >> t;
	int n=s.length(), m=t.length();
	vector<vi> dp(n+1, vi(m+1));
	vector<ii> ch = {{1, 0}, {0, 1}, {1, 1}};
	ii cur, next;
	dbg(s, t);
	rep(i, 0, n){
		rep(j, 0, m){
			cur = {i, j};
			rep(c, 0, 3)	if(c != 2 || s[i]==t[j]){
				next = cur + ch[c];
				if(next.fi>n || next.se>m)	continue;
				
				dp[next.fi][next.se] = max(dp[next.fi][next.se], dp[cur.fi][cur.se] + (c==2));
			}
		}
	}
	rep(i, 0, n)
		dp[i+1][m] = max(dp[i+1][m], dp[i][m]);
	rep(j, 0, m)
		dp[n][j+1] = max(dp[n][j+1], dp[n][j]);
		
	dbg(dp);
	string sol="";
	cur = {n, m};
	while(cur.fi && cur.se){
		rep(c, 0, 3){
			next = cur;
			next.fi -= ch[c].fi;
			next.se -= ch[c].se;
			if(dp[next.fi][next.se] + (c==2) == dp[cur.fi][cur.se]){
				if(c==2)
					sol.push_back(s[next.fi]);
				cur = next;
				break;
			}
		}
	}
	dbg(sol);
	reverse(sol.begin(), sol.end());
	cout << sol << '\n';
}



Measured memory_bytes: 38452
#include<bits/stdc++.h>
using namespace std;
int main() {
  int n,a;
  cin>>n;
  double d=0;
  for(int i=0;i<n;i++){
    cin>>a;
    d+=1.0/a;
  };
  cout<<fixed<<setprecision(10)<<1.0/d<<endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
  int A,B,C;

  cin>>A>>B>>C;
  
  int num=A;

  for(int i=0;i<B;i++){
    num%=B;
    if(num==C){
      cout<<"YES"<<endl;
      return 0;
    }
    num+=A;
  }

  cout<<"NO"<<endl;

  return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define N (1<<21)
#define INF 1000000009
#define MOD 1000000007
typedef long long int ll;
#define sd(x) scanf("%d",&x)
#define sd2(x,y) scanf("%lld%lld",&x,&y)
#define sd3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define pf(x) printf("%d",x);
#define pf2(x,y) printf("%d %d\n",x,y);
#define pf3(x,y,z) printf("%d %d %d\n",x,y,z);
#define fi first
#define se second
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define tr(x) cout<<x<< endl;
#define tr2(x,y) cout<<x<<" "<<y<<" " << endl;
#define tr3(x,y,z) cout<<x<<" "<<y<<" "<<z<<endl;
#define tr4(x,y,z,a) cout<<x<<" "<<y<<" "<<z<<  " " << a << " " << endl;

ll dp1[N],dp2[N],n;
bool a[22][22];
int main(){ 
    int i,j,t,x,y;
    cin >> n;
    for(i=1; i<=n; i++){
        for(j=0; j<n; j++){
            sd(a[i][j]);
        }
    }
    for(i=1; i<=n; i++){
        for(int mask=1; mask<(1<<n); mask++){
            if(i==1){
                if(__builtin_popcount(mask)!=1){continue;}
                for(int j=0; j<n; j++){
                    if(mask&(1<<j) && a[i][j]){
                        // tr(j);
                        dp1[mask]=1;
                    }   
                }
            }
            
            else{
                if(__builtin_popcount(mask)<i){continue;}
                for(int j=0; j<n; j++){
                    if(mask&(1<<j) && a[i][j]){
                        dp1[mask]+=dp2[mask^(1<<j)];
                    }
                }
            }
            dp1[mask]%=MOD;
            // tr3(i,mask,dp1[mask]);
        }
        
        for(int mask=1; mask<(1<<n); mask++){
            dp2[mask] = dp1[mask];
            dp1[mask] = 0;
        }
    }
    tr(dp2[(1<<n)-1]);
    return 0;
}

Measured memory_bytes: 33024
/*********************"ANJAN AGARWALA"************************
***************************@anjn98****************************/

//#define opti
#ifdef opti
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#endif

#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;

typedef long long int ll;
typedef unsigned long long int ull;
ll power(ll x,ll y,ll p){ll r=1; x=x%p; while(y){ if(y&1) r= r*x%p; y=y>>1; x=x*x%p; } return r; }
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

#define IO 				ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define all(v) 			v.begin(),v.end()
#define PR(a) 			cout<<"("<<a<<")";
#define ED 				cout<<'\n';
#define endl 			'\n'
#define loop(j,a,n) 	for(int j=a;j<=n;j++)
#define loop1(j,a,n) 	for(int j=a;j>=n;j--)
#define fr1(j,n) 		for(int j=0;j<n;j++)
#define fr(n) 			for(int i=0;i<n;i++)
#define trav(x,s)       for(auto x:s)
#define PB 				push_back
#define MP 				make_pair
#define pii 			pair<int,int>
#define pll 			pair<long long int,long long int>
#define F 				first
#define S 				second 
#define binf 			2000000000000000001
#define mod 			1000000007

const int  M=1,N=1e5+9;
ll dp[N][3],a[N][3];

int32_t main()
{	
	IO
    int n;cin>>n;
    fr(n)fr1(j,3) cin>>a[i][j];
    
    fr(3)dp[0][i]=a[0][i];

    loop(i,1,n-1)
    {
        dp[i][0]=a[i][0]+ max(dp[i-1][1],dp[i-1][2]);
        dp[i][1]=a[i][1]+ max(dp[i-1][0],dp[i-1][2]);
        dp[i][2]=a[i][2]+ max(dp[i-1][1],dp[i-1][0]);
    }
    ll ans=0;
    fr(3) ans=max(ans,dp[n-1][i]);
    cout<<ans<<endl;

}

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

#define rep(i,a,b)      for(int i=a;i<=b;i++)
#define revp(i,a,b)     for(int i=b;i>=a;i--)

vector<int> A = {1,3,1,2,1,2,1,1,2,1,2,1};
int a,b;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin>>a>>b;
    if(A[a-1]==A[b-1])
        cout<<"Yes";
    else
        cout<<"No";
}




Measured memory_bytes: 256
#include <iostream>
#define endl '\n'
#include <algorithm>
using namespace std;


int main()
{
    int n,k;
    cin >> n;
    pair<int,int> a[n];
    for(int i = 0; i < n; i++)
    {
        cin >> k;
        a[i] = {k,i};
    }
    sort(a,a+n);
    int c = 0;
    for(int i = 0; i < n; i++)
    {
        int j = a[i].second;
        if(i%2 == 0 && j%2 != 0)
            c++;
        if(i%2 != 0 && j%2 == 0)
            c++;
    }
    cout << c/2 << endl;
    return 0;
}


Measured memory_bytes: 1024
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    private int cnt;
    private ArrayList<Integer> G = null;

    public Main(int n, int[] num) {
        this.cnt = 0;
        this.G = new ArrayList<>();
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] num = new int[n];
        for (int i = 0; i < n; i++) {
            num[i] = in.nextInt();
        }
        Main test = new Main(n, num);
        test.shellSort(num, n);
        System.out.println(test.G.size());
        for (int i = test.G.size() - 1; i >= 0; i--) {
            System.out.print(test.G.get(i));
            if (i != 0) System.out.print(" ");
        }
        System.out.println();
        System.out.println(test.cnt);
        for (int i = 0; i < n; i++) {
            System.out.println(num[i]);
        }
    }

    private void insertionSort(int[] num, int n, int g) {
        for (int i = g; i < n; i++) {
            int key = num[i];
            int j = i - g;
            while (j >= 0 && num[j] > key) {
                num[j + g] = num[j];
                j -= g;
                cnt++;
            }
            num[j + g] = key;
        }
    }

    private void shellSort(int[] num, int n) {
        for (int h = 1; ; ) {
            if (h > n) break;
            G.add(h);
            h = 3 * h + 1;
        }

        for (int i = G.size() - 1; i >= 0; i--) {
            insertionSort(num, n, G.get(i));
        }
    }
}


Measured memory_bytes: 299632
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<ctime>
#include<bitset>
#include<string>
#include<vector>
#include<cctype>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define per(i,a,b) for(int i = (a); i >= (b); i--)
#define mst(a,b) memset(a,b,sizeof(a));
#define clr(a) mst(a,0);
#define pb  push_back
#define mp  make_pair
#define first fi
#define second se
int dir[4][2] = {1,0,-1,0,0,1,0,-1};
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
ll _gcd(ll a,ll b){return b?_gcd(b,a%b):a;}
const double PI = acos(-1);
//head
const int maxn = 1e5 + 11;
int a[maxn],b[maxn],ans = 0;
int main(int argc, char const *argv[]){
	

	string str; cin >> str;
	if(str.length() == 2){ 
		cout << str << endl;
	}else{
		reverse(str.begin(),str.end());
		cout << str << endl;
	}
	return 0;
}












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

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< pii >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; cin >> x;
#define int2(x, y) Int(x); Int(y);
#define int3(x, y, z) Int(x); int2(y, z);
#define in(x, a, b) ((a) <= (x) && (x) < (b))
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second
#define Decimal fixed << setprecision(10)

//int dxy[5] = {0, 1, 0, -1, 0};
// cmd

double solve(int time, double el, double er, double l, double r, double score, double p)
{
    double m = (l + r) / 2.0, t = (er + el) / 2.0, ret = 0.0;
    if (!time) return (el <= m && m <= er) ? score : ret;
    if (el <= l && r <= er) return score;
    if (r < el || er < l) return 0.0;
    double ml = (l + m) / 2.0, mr = (r + m) / 2.0;
    ret += solve(time-1, el, er, l, m, score * ((abs(mr - t) <= abs(ml - t)) ? p : 1 - p), p);
    ret += solve(time-1, el, er, m, r, score * ((abs(mr - t) <= abs(ml - t)) ? 1 - p : p), p);
    return ret;
}

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

    int3(k, r, l);
    double p, e, t;
    cin >> p >> e >> t;

    cout << Decimal << solve(k, t - e, t + e, r, l, 1.0, p) << endl;

    return 0;
}




Measured memory_bytes: 3300
def insertionSort(a, n, g):
  global cnt
  for i in range(g, n):
    v = a[i]
    j = i - g
    while j >= 0 and a[j] > v:
      a[j + g] = a[j]
      j = j - g
      cnt += 1
    a[j + g] = v

def shellSort(a, n):
  global cnt
  cnt = 0
  g = []
  h = 1
  while h <= len(a):
    g.append(h)
    h = 3 * h + 1
  g.reverse()
  m = len(g)
  for i in range(0, m):
    insertionSort(a, n, g[i])
  print(m)
  print(" ".join(map(str, g)))
  print(cnt)
  for c in a:
    print(c)

n = int(input())
a = [int(input()) for _ in range(n)]
shellSort(a,n)


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

using namespace std;

class infomation{
public:
    int c,s,f;
    infomation(){
        c = 0, s = 0, f = 0;
    };
};

int main(){
    int n;
    cin >> n;
    vector<int> t(n,0);
    vector<infomation> info(n);
    for(int i = 0; i< n-1; i++){
        cin >> info[i].c >> info[i].s >> info[i].f;
    }

    for(int i = 0; i < n-1; i++){
        t[i] += info[i].s;
        t[i] += info[i].c;
        for(int j = i+1; j < n-1; j++){
            if(t[i]-info[j].s <= 0){
                t[i] = info[j].s;
                t[i] += info[j].c;
            }
            else if((t[i]-info[j].s) % info[j].f != 0){
                t[i] = ((t[i] - info[j].s)/info[j].f + 1) * info[j].f + info[j].s;
                t[i] += info[j].c;
            }
            else t[i] += info[j].c;
        }
    }

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


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<deque>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
#define FOR(i,n) for(int (i)=0;(i)<(n);(i)++)
#define FOR1(i,n) for(int (i)=1;(i)<(n);(i)++)
#define eFOR(i,n) for(int (i)=0;(i)<=(n);(i)++)
#define eFOR1(i,n) for(int (i)=1;(i)<=(n);(i)++)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i) sort((i).begin(),(i).end(), greater<int>());
#define YES(i) cout << ((i) ? "Yes" : "No") << endl;
constexpr auto INF = 1000000000;
constexpr auto LLINF = 922337203685477580;//7;
constexpr auto mod = 1000000007;

class unionfind {
	VI par, rank;
public:
	void init(int N) {
		par.clear();
		rank.clear();
		for (int i = 0; i < N; i++) par.push_back(i);
		for (int i = 0; i < N; i++) rank.push_back(1);
	}
	int root(int x) {
		if (par[x] == x)return x;
		return par[x] = root(par[x]);
	}
	int size(int x) {
		if (par[x] == x)return rank[x];
		return size(par[x]);
	}
	void unite(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		if (rx == ry)return;
		if (rank[rx] < rank[ry]) {
			par[rx] = ry;
			rank[ry] += rank[rx];
		}
		else {
			par[ry] = rx;
			rank[rx] += rank[ry];
		}
	}
	bool same(int x, int y) {
		return root(x) == root(y);
	}
};

int main() {

	int n, m;
	cin >> n >> m;
	VI x(m), y(m), z(m);
	FOR(i, m) {
		cin >> x[i] >> y[i] >> z[i];
		x[i]--; y[i]--;
	}

	unionfind UF;
	UF.init(n);
	FOR(i, m)UF.unite(x[i], y[i]);
	set<int> ans;
	FOR(i, n)ans.insert(UF.root(i));
	cout << ans.size() << endl;
}

Measured memory_bytes: 6904
#include <iostream>
#include <cstdio>
using namespace std;
int N;
int p[20001],a[20001],b[20001];
int main(){
  scanf("%d",&N);
  for(int i=1;i<=N;i++)scanf("%d",&p[i]);
  for(int i=1;i<=N;i++){
    a[i]=N*i;
    b[i]=N*(N+1-i);
  }
  for(int i=1;i<=N;i++){
    a[p[i]]+=i;
  }
  for(int i=1;i<=N;i++)printf("%d%c",a[i],i==N?'\n':' ');
  for(int i=1;i<=N;i++)printf("%d%c",b[i],i==N?'\n':' ');
  return 0;
}


Measured memory_bytes: 896
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
struct node{
    int key;
    node* parent,*left,*right;
};
node *root=NULL;
node * pre;
void Insert(int key){
    node * temp=new node;
    temp->key=key;
    temp->left=NULL;
    temp->right=NULL;

    if(root==NULL){
        root=temp;
        return ;
    }
    else{
        pre=root;
        while(1){
            if (key<pre->key){
                if (pre->left==NULL){
                    pre->left=temp;
                    temp->parent=pre;
                    return;
                }
                else
                    pre=pre->left;
            }
            else if(key > pre->key){
                if (pre->right==NULL){
                    pre->right=temp;
                    temp->parent=pre;
                    return;
                }
                else
                    pre=pre->right;
            }
            else
                return;
        }
    }
}
void Print_in(node* r){
    if(r->left!=NULL){
        Print_in(r->left);
    }
    cout<<" "<<r->key;
    if(r->right!=NULL){
        Print_in(r->right);
    }

}
void Print_pre(node *r){
    cout<<" "<<r->key;
    if(r->left!=NULL){
        Print_pre(r->left);
    }
    if(r->right!=NULL){
        Print_pre(r->right);
    }
}
void Print(node * r){
    Print_in(r);
    cout<<endl;
    Print_pre(r);
    cout<<endl;
}
int main(){
    int n;
    string cmd;
    int key;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>cmd;
        if(cmd[0]=='i'){
            cin>>key;
            Insert(key);
        }
        else if(cmd[0]=='p'){
            Print(root);
        }
    }
    return 0;
}



Measured memory_bytes: 26552
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7
    #epsilon = 10**-9

    d = int(input())
    c = list(map(int, input().split()))
    last = [0]*26
    s = [list(map(int, input().split())) for _ in range(d)]
    res = 0
    for i in range(d):
        t = int(input())
        last[t-1] = i+1
        res += s[i][t-1]
        for j in range(26):
            res -= c[j] * (i+1-last[j])
        print(res)

if __name__ == '__main__':
    main()

Measured memory_bytes: 9708
#include<bits/stdc++.h> 
#define de() cout<<"test"<<"\n"  
#define ll long long 
using namespace std;
const int maxn=(1<<17)+10;
const int mod=1e9+7;
int n,m,a[maxn],cnt[maxn];
ll inv[maxn],mul[maxn],dp[17][maxn],er[maxn],ans;
ll poww(ll x,ll k) {
	ll ans=1;while(k) {if(k&1) ans=ans*x%mod;x=x*x%mod;k>>=1;}return ans;
}
ll C(int a,int b) {
	if(b>a) return 0;
	return mul[a]*inv[b]%mod*inv[a-b]%mod;
}
bool cmp(int a,int b) {return a>b;} 

int main() 
{
	scanf("%d%d",&n,&m);er[0]=1;for(int i=1;i<=n;++i) er[i]=er[i-1]*2%mod;
	for(int i=1;i<=m;++i) scanf("%d",&a[i]);
	mul[0]=1;for(int i=1;i<=(1<<n);++i) mul[i]=mul[i-1]*i%mod,cnt[i]=cnt[i>>1]+(i&1);
	inv[1<<n]=poww(mul[1<<n],mod-2);
	for(int i=(1<<n);i;i--) inv[i-1]=inv[i]*i%mod;inv[0]=1;
	sort(a+1,a+m+1,cmp);dp[0][0]=1;
	for(int i=0;i<m;++i) {
		for(int j=0;j<er[n];++j) {
			for(int k=0;k<n;++k) {
				if(((j>>k)&1)) continue ;
				ll t=er[n]-j-1;
				dp[i+1][j^(1<<k)]=(dp[i+1][j^(1<<k)]+dp[i][j]*C(t-a[i+1]+1,(1<<k)-1)%mod*mul[1<<k]%mod)%mod;
			}
			dp[i+1][j]=(dp[i][j]+dp[i+1][j])%mod;
		}
	}
	for(int i=0;i<er[n];++i) {
		ll tmp=dp[m][i]*mul[er[n]-i-1]%mod;
		if(cnt[i]&1) {
			ans=(ans-tmp+mod)%mod;
		}else ans=(ans+tmp)%mod;
	}
	ans=ans*er[n]%mod;
	cout<<ans<<"\n";
	return 0;
}



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

#define SIZE 200010

typedef struct _Edge {
    int to, next;
} Edge;

Edge edge[SIZE << 1];
int head[SIZE], edgePt, vertexNum;
int dp[SIZE], maxLen;

void addEdge(int from, int to) {
    edge[edgePt] = {to, head[from]};
    head[from] = edgePt++;
}

void dfs(int cntPt, int fatherPt) {
    dp[cntPt] = 0;
    for (int i = head[cntPt]; i != -1; i = edge[i].next) {
        int nextPt = edge[i].to;
        if (nextPt == fatherPt)
            continue;
        dfs(nextPt, cntPt);
        int cntLen = dp[nextPt] + 1;
        if (cntLen + dp[cntPt] > maxLen)
            maxLen = cntLen + dp[cntPt];
        dp[cntPt] = max(dp[cntPt], cntLen);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    memset(head, -1, sizeof(head));
    edgePt = 0;
    cin >> vertexNum;
    for (int i = 1; i < vertexNum; i++) {
        int from, to;
        cin >> from >> to;
        from--; to--;
        addEdge(from, to);
        addEdge(to, from);
    }

    maxLen = 0;
    dfs(0, -1); maxLen++;
    int ans = (maxLen % 3 != 2);
    cout << (ans ? "First\n" : "Second\n");
    return 0;
}


Measured memory_bytes: 13952
#include <bits/stdc++.h>
#define PI 3.14159265358979323846
#define MAXINF (1e18L)
#define INF (1e9L)
#define EPS (1e-9)
#define MOD ((ll)(1e9+7))
#define REP(i, n) for(int i=0;i<int(n);++i)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define ALL(v) v.begin(),v.end()
#define FIND(v,x) (binary_search(ALL(v),(x)))
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v));reverse(ALL(v))
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define pb push_back
#define fi first
#define se second
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
template<class T> inline bool chmin(T& a, T b){return a>b ? a=b, true : false;}
template<class T> inline bool chmax(T& a, T b){return a<b ? a=b, true : false;}
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;
 
const ll M = 3500;
 
int main(void)
{
    ll N;
    cin >> N;
    Rep(i, 1, M+1){
        ll lb = 1, ub = M;
        while(ub-lb > 1){
            ll mid = (lb+ub) / 2;
            ll a = 4*i*mid-i*N-mid*N;
            if(a > 0) ub = mid;
            else lb = mid;
 
            if(a <= 0) continue;
 
            if(((i*ub*N) % a) == 0){
                ll k = (i*ub*N)/a;
                if(4*i*ub*k == (i*ub + ub*k + k*i)*N){
                    pr(i, ub, k);
                    return 0;
                }
            }
        }
    }
}

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

int main() {
	int A, B;
	cin >> A >> B;
	if (A > 12) {
		cout << B << endl;
	}
	else if (5 < A && A < 13) {
		cout << B / 2 << endl;
	}
	else {
		cout << 0 << endl;
	}
}

Measured memory_bytes: 256
/*
  AOJ 0114
  Electric Fly
 */
#include <stdio.h>

long long gcd(long long x, long long y){
	return y == 0 ? x: gcd(y, x%y);
}


long long lcm(long long x,long long y)
{
  return(x/gcd(x,y)*y);
}

int modori1(int a,int b)
{
  long long i,product;

  product=a;i=1;
  while((product % b) != 1)
    {
      i++;product*=a;product=product % b;
    }
  return(i);
}
main()
{
  int a1,m1,a2,m2,a3,m3,r1;
  long long r2,r3,ret;

  while(EOF!=scanf("%d %d %d %d %d %d",&a1,&m1,&a2,&m2,&a3,&m3) && 
	(a1||m1||a1||m2||a3||m3))
    {
  r1=modori1(a1,m1);
  //printf("%d %d %d\n",a1,m1,r1);
  r2=modori1(a2,m2);
  //printf("%d %d %d\n",a2,m2,r2);
  r3=modori1(a3,m3);
  //printf("%d %d %d\n",a3,m3,r3);
  ret=lcm(lcm(r1,r2),r3);
  printf("%lld\n",ret);
    }
}

Measured memory_bytes: 600
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQG = priority_queue<T, vector<T>, greater<T> >;
const int INF = 100010001;
const ll LINF = (ll)INF*INF*10;
template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second;}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second;}

struct edge {
    int to;
    int cost;
    edge(int x=0, int y=0):to(x), cost(y) {}
};

vector<vector<edge> > G; // resizeの必要あり


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int v, e;
    cin >> v >> e;
    G.resize(v);
    rep(i, e) {
        int s, t, d;
        cin >> s >> t >> d;
        G[s].emplace_back(t, d);
    }

    vector<vvi> dp(v, vvi(1<<v, vi(v, INF)));
    rep(i, v) {
        dp[i][1<<i][i] = 0;
    }
    rep(i, 1<<v) {
        rep(j, v) if((i>>j)&1) {
            int now = i^(1<<j);
            for(edge ne:G[j]) if((now>>ne.to)&1) rep(hhh, v) {
                dp[hhh][i][j] = min(dp[hhh][i][j], dp[hhh][now][ne.to] + ne.cost);
            }
        }
    }
    int ans = INF;
    rep(i, v) {
        for(edge ne:G[i]) {
            ans = min(ans, dp[i][(1<<v)-1][ne.to] + ne.cost);
        }
    }
    if(ans == INF) ans = -1;
    cout << ans << endl;


}


Measured memory_bytes: 56028
#include <stdio.h>
#define N 130

#define WHITE 0
#define BLACK 1
#define GRAY 2


int f[N],d[N],f[N],e[N];
int color[N];
int time;
int a[N],b[N],c[N];
int B[N][N];



main()
{
  
  
  int n,i,j,u;
  int A[N][N];
  
  
  
  scanf("%d",&n);
  
  for(i = 1; i <= n; i++){
    scanf("%d%d",&a[i],&b[i]);
    for(j = 1; j <= b[i]; j++){
      scanf("%d",&c[j]);
      A[a[i]][c[j]] = BLACK;
      B[a[i]][j] = c[j];
    }  
  }
  
  dfs(n);

  return 0;
}



int dfs(int n)
{

  int i,u;

  for(i = 1; i <= n; i++){
    u = a[i];
    color[u] = WHITE;
    time = 0;
  }
  
  for(i = 1; i <= n; i++){
    u = a[i];
    if(color[u] == WHITE){
      Visit(u);
    }
    printf("%d %d %d\n",u,d[u],f[u]);
  }
}

int Visit(int u)
{
  
  int i,v;
 
  color[u] = GRAY;
    d[u] = ++time;

    for(i = 1; i <= b[u]; i++){
      v = B[u][i];
      if(color[v] == WHITE){
	Visit(v);
      }
    }
    color[u] = BLACK;
    f[u] = ++time;

 
}

Measured memory_bytes: 652
S = input()
num = len(S) - 1 # 隙間の個数

all_value = 0
for i in range(2 ** num):
    op = [''] * num
    for j in range(num):
        if((i >> j) & 1):
            op[num - 1 - j] = "+"


    formula = ""
    for p_n, p_o in zip(S, op + [""]):
        formula += (p_n + p_o)

    all_value += eval(formula)

print(all_value)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
struct Fast {
    Fast() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} fast;

void yes() {
    cout << "Yes" << endl;
    exit(0);
}
void no() {
    cout << "No" << endl;
    exit(0);
}
#define REP(i, n) for (long long i = 0; i < (n); i++)

long long modpow(long long m, long long n) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        long long t = modpow(m, n / 2);
        return t * t;
    } else {
        return modpow(m, n - 1) * m;
    }
}
typedef long long ll;
typedef pair<ll, ll> P;
map<long long, long long> cnt;
void primeFactors(long long n) {
    while (n % 2 == 0) {
        cnt[2]++;
        n = n / 2;
    }
    for (int i = 3; i <= sqrt(n); i = i + 2) {
        while (n % i == 0) {
            cnt[i]++;
            n = n / i;
        }
    }
    if (n > 2) {
        cnt[n]++;
    }
}
signed main() {
    ll n;
    cin >> n;
    map<string, ll> cnt;
    REP(i, n) {
        string s;
        cin >> s;
        cnt[s]++;
    }
    cout << "AC x ";
    cout << cnt["AC"] << endl;
    cout << "WA x ";
    cout << cnt["WA"] << endl;
    cout << "TLE x ";
    cout << cnt["TLE"] << endl;
    cout << "RE x ";
    cout << cnt["RE"] << endl;
}

Measured memory_bytes: 3648