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

template <class T>
inline bool read(T &ret)
{
    char c;
    int sgn;
    if (c = getchar(), c == EOF)
    {
        return 0;
    }
    while (c != '-' && (c < '0' || c > '9'))
    {
        c = getchar();
    }
    sgn = (c == '-') ? -1 : 1;
    ret = (c == '-') ? 0 : (c - '0');
    while (c = getchar(), c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0');
    }
    ret *= sgn;
    return 1;
}

template <class T>
inline void write(T x)
{
    if (x > 9)
    {
        write(x / 10);
    }
    putchar(x % 10 + '0');
}

const int MAXN=1010;
int n,ans;
bool vised[MAXN];
queue<int> que[MAXN];

int main()
{
    read(n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<n;j++)
        {
            int sr;
            read(sr);
            que[i].push(sr);
        }
    }
    ans=0;
    while(true)
    {
        for(int i=1;i<=n;i++)
            vised[i]=false;
        bool pd=false;
        for(int i=1;i<=n;i++)
        {
            if(!que[i].empty()&&!vised[i])
            {
                int cc=que[i].front();
                if(!vised[cc]&&i==que[cc].front())
                {
                    que[i].pop();
                    que[cc].pop();
                    vised[i]=true;
                    vised[cc]=true;
                    pd=true;
//                    cout<<i<<" "<<cc<<" "<<ans<<endl;
                }
            }
        }
        if(!pd)
            break;
        ans++;
    }
    for(int i=1;i<=n;i++)
        if(!que[i].empty())
        {
            cout<<"-1"<<endl;
            return 0;
        }
    cout<<ans<<endl;
}


Measured memory_bytes: 6784
#include <bits/stdc++.h>
#define ll long long

using namespace std;
double x[20][20];

int main()
{
    int n,D;  cin >> n >> D;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<D;j++){
            cin >> x[i][j];
        }
    }
    int Ans =0 ;
    for(int i = 0;i<n;i++){
        for(int j = i + 1;j<n;j++){
            double Res = 0;
            for(int k = 0;k<D;k++){
                Res+=(x[i][k] - x[j][k]) * (x[i][k] - x[j][k]);
            }
            Res = sqrt(Res);
            double inpart;
            if(modf(Res , &inpart) == 0.0)  Ans++;
        }
    }
    cout << Ans;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define F first
#define S second 
#define mp make_pair
#define pb push_back
#define pf push_front
#define speed_up ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define debug cerr << "OK\n";
#define ub upper_bound
#define lb lower_bound
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vpii;
typedef set <int> si;
typedef set <ll> sll;
typedef multiset <int> msi;
typedef multiset <ll> msll;
typedef map <int, int> mi;
typedef map <ll, int> mll;
 
const int N = 1e6 + 2;
const int M = 1e5 + 2;
const int mod = 998244353;
const int inf = 1e9;
const ll INF = 1e16;
 
void data() {
    #ifdef PC
        freopen("main.in", "r", stdin);
        freopen("main.out", "w", stdout);
    #endif
}
 
template <typename T>
void scerr(T nums) {
	for (auto it : nums)
		cerr << it << " | ";
	cerr << "\n";
}
 
string s, t;
 
int main() {
	data();
	cin >> s >> t;
	cout << t << s;
}
 
/*
	Timus: 288481RF
	CodeForces: __fractal
*/


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

int main(){
  int a,b,c,d;
  cin >> a >> b >> c >> d;

	if(abs(b-a) <= d && abs(c-b) <= d) cout << "Yes" << endl;
	else if(abs(c-a) <= d) cout << "Yes" << endl;
	else cout << "No" << endl;
	
  return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N; cin >> N;
  bool F[N][10]; CLR(F);
  FOR(i,0,N) FOR(j,0,10) cin >> F[i][j];
  int P[N][10];
  FOR(i,0,N) FOR(j,0,11) cin >> P[i][j];
  int ans = -1e9;
  FOR(i,0,1<<10) {
    bool open[10]; CLR(open);
    bool ok = false;
    FOR(j,0,10) {
      if((i>>j)&1) {
        open[j] = true;
        ok = true;
      }
    }
    if(!ok) continue;
    int cnt[N]; CLR(cnt);
    FOR(j,0,N) {
      FOR(k,0,10) {
        if(F[j][k] && open[k]) cnt[j]++;
      }
    }
    int p = 0;
    FOR(j,0,N) p += P[j][cnt[j]];
    ans = max(ans, p);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main() {
	int i, n;
	double Y = 0, x[10];
	char y[10][4];

	scanf("%d", &n);

	for (i = 0; i < n; i++) {
		scanf("%lf %s", &x[i], &y[i][0]);
		if (y[i][0] == 'J') {
			Y += x[i];
		}
		else {
			Y = Y + x[i] * 380000.0;
		}
	}

	printf("%lf", Y);

	return 0;
}

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

int main() {
  int N, M;
  cin >> N >> M;
  map<int, bool> A;
  map<int, int> Pcount;
  int p = 0;
  int count = 0;
  map<int, int> acs;
  for (int i = 0; i < M; i++) {
    int mondai;
    string answer;
    cin >> mondai >> answer;
	if (answer == "AC" && !A[mondai]){
      count++;
      A[mondai] = true;
      acs[mondai] = i;
      p += Pcount[mondai];
    } else if (answer == "WA" && !A[mondai]) {
      Pcount[mondai]++;
    }
  }
  
  cout << count << " " << p <<endl;
}

Measured memory_bytes: 14336
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <numeric>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

#define rep(i, N) for(int i = 0; i < N; ++i)

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

#define IN(l, r, x) ((l) <= (x) && (x) < (r))

using P = pair<s64, s64>;

void dijkstra(const vector< vector< P > >& g, vs64& d, int s)
{
    rep (i, d.size()) d[i] = 1e18;
    d[s] = 0;

    priority_queue<P, vector<P>, greater<P> > pq;
    pq.push(P{d[s], s});

    while (!pq.empty())
    {
        auto p = pq.top(); pq.pop();
        s64 from = p.second;
        s64 d1 = p.first;
        if (d[from] < d1) continue;

        for (auto& x : g[from])
        {
            s64 to = x.first;
            s64 d2 = x.second;
            if (d[to] > d1 + d2)
            {
                d[to] = d1 + d2;
                pq.push(P{d[to], to});
            }
        }
    }
}

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

    int n, m, s, t;
    cin >> n >> m >> s >> t;
    --s, --t;

    vector< vector< P > > g1(n), g2(n);
    rep (i, m)
    {
        int u, v;
        s64 a, b;
        cin >> u >> v >> a >> b;
        --u, --v;
        g1[u].emplace_back(v, a);
        g1[v].emplace_back(u, a);
        g2[u].emplace_back(v, b);
        g2[v].emplace_back(u, b);
    }

    vs64 d1(n), d2(n);
    dijkstra(g1, d1, s);
    dijkstra(g2, d2, t);

    vs64 d(n, 1e15);
    rep (i, n)
    {
        d[i] -= d1[i] + d2[i];
    }

    for (int i = n - 2; i >= 0; --i)
    {
        d[i] = MAX(d[i], d[i + 1]);
    }

    rep (i, n)
    {
        cout << d[i] << "\n";
    }
    return 0;
}



Measured memory_bytes: 19016
require 'openssl'
require 'set'; require 'prime'
INF=Float::INFINITY; MOD=998244353
n = gets.chomp.to_i
d = gets.chomp.split.map(&:to_i)

if d[0] != 0
  puts 0
  exit
end

h = Hash.new(0)
d.each do |num|
  h[num] += 1
end

if h[0] != 1
  puts 0
  exit
end

ans = 1

ha = h.sort_by{|k,v| k}
(ha.size-1).times do |i|
  if ha[i][0] + 1 != ha[i+1][0]
    puts 0
    exit
  end
  # p [ha[i][1], ha[i+1][1], ha[i][1].to_bn.mod_exp(ha[i+1][1], MOD)]
  # ans = ans * ha[i][1].to_bn.mod_exp(ha[i+1][1], MOD) % MOD
  ans = (ans * (ha[i][1] ** ha[i+1][1])) % MOD
end

puts ans




Measured memory_bytes: 24144
#include<bits/stdc++.h>
using namespace std;
#define MAX_V 300
#define INF (1e8)
struct edge{ int to,cap,rev; };
 
int V,E;
vector<edge> G[MAX_V];
bool used[MAX_V];
 
void add_edge(int from,int to,int cap){
  G[from].push_back((edge){to,cap,(int)G[to].size()});
  G[to].push_back((edge){from,0,(int)G[from].size()-1});
}
 
int dfs(int v,int t,int f){
  if(v == t) return f;
  used[v] = true;
  for(int i = 0 ; i < (int)G[v].size() ; i++){
    edge &e = G[v][i];
    if(!used[e.to] && e.cap > 0){
      int d = dfs(e.to,t,min(f,e.cap));
      if(d > 0){
        e.cap -= d;
        G[e.to][e.rev].cap += d;
        return d;
      }
    }
  }
  return 0;
}
 
int max_flow(int s,int t){
  int flow = 0;
  for(;;){
    memset(used,false,sizeof(used));
    int f = dfs(s,t,INF);
    if(f == 0) return flow;
    flow += f;
  }
}

int N,M;
int t[200][200];

bool check(int mid){
  for(int i=0;i<MAX_V;i++)G[i].clear();
  
  V=N+M+3;
  int si=V-3;
  int ti=V-2;
  int xx=V-1;
  
  for(int i=0;i<N;i++){
    for(int j=0;j<M;j++){
      if(t[i][j] > mid)continue;
      add_edge(i,N+j,1);
    }
  }
  for(int i=0;i<N;i++){
    int cap=M/N;
    add_edge(si, i,cap);
  }
  for(int i=0;i<M;i++){
    add_edge(N+i,ti,1);
  }
  if(M%N>0){
    add_edge(si,xx,M%N);
    for(int i=0;i<N;i++){
      add_edge(xx,i,1);
    }
  }
  if( max_flow(si,ti) == M )return true;
  return false;
}

int main(){
  cin>>N>>M;
  for(int i=0;i<N;i++){
    for(int j=0;j<M;j++){
      cin>>t[i][j];
    }
  }
  if(M%N==0)cout<<0<<endl;
  else cout<<1<<endl;
  
  int L=1,R=1e9,M;
  while(L<R){
    M=(L+R)/2;
    if(check(M))R=M;
    else L=M+1;
  }
  cout<<L<<endl;
  return 0;
}

Measured memory_bytes: 3332
import java.io.{BufferedReader, InputStreamReader}
import java.util.Arrays.binarySearch

object Main extends App {
  val in = new BufferedReader(new InputStreamReader(System.in))
  val n = in.readLine.toInt
  val a, b, c = in.readLine.split(" ").map(_.toLong).sorted
  
  val ans = {
      var posA = 0
      var posC = 0

      def findA(tar:Long):Int = {
        val pa = binarySearch(a, posA, a.length, tar - 1)
        posA = if(pa > -1) pa else ~pa
        while(posA < n && a(posA) < tar) posA += 1
        posA
      }
      def findC(tar:Long):Int = {
        val pc = binarySearch(c, posC, c.length, tar - 1)
        posC = if(pc > -1) pc else ~pc
        while(posC < n && c(posC) <= tar) posC += 1
        posC
      }

      b./:(0L)((acc,e) => {
        val ac = findA(e)
        val cc = n - findC(e)

        acc +  ac.toLong * cc.toLong
      })
    }

  println(ans)
}

Measured memory_bytes: 81456
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, a, b;
  cin >> n >> a >> b;
  
  int plan1Fee = a * n;
  int plan2Fee = b;
  
  if (plan1Fee < plan2Fee)
  {
    cout << plan1Fee;
  }
  else
  {
    cout << plan2Fee;
  }
}

Measured memory_bytes: 3628
#define IO std::ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,a,b,ans;
int main(){
	IO;
	cin>>n>>a>>b;
	if(b<=a){
		cout<<n+1<<endl;
	}
	else{
		if(n+1>=a){
			ll h=n+1-a;
			ans=(h/2)*(b-a);
			if(h%2)ans++;
		}
		cout<<max(n+1,ans+a)<<endl;
	}
}

Measured memory_bytes: 764
#include <iostream>

using namespace std;

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

    int d[n];
    for (int i = 0; i < n; i++) cin >> d[i];

    int bucket[110] = {0};
    for (int i = 0; i < n; i++) bucket[d[i]]++;

    int cnt = 0;
    for (int i = 1; i <= 100; i++) {
        if (bucket[i]) cnt++;
    }

    cout << cnt << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include<list>
#include <algorithm>
#include <string>
#include <math.h>
#include<map>
#include <utility>
#include <cstring>
#include <iomanip>
#include<queue>
using namespace std;
#define REP(i,k,n) for(int i=k;i<n;i++)
 
#define INF 1000000000
typedef long long  ll;
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
#define MOD 1000000007

template<typename T>
int vector_finder(std::vector<T> vec, T number) {
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return 1;
  }
  else { // 発見できなかったとき
    return 0;
  }
}

template<typename T>
T gcd(T a,T b){
	if(b>0){
		return gcd(b, a % b);
	}else{
		return a;
	}
}

template<typename T>
T lcm(T a,T b){
	T g = gcd(a, b);
	return a /g* b ;
}

void clear( std::queue<pair<int,int> > &q )
{
   std::queue<pair<int,int> > empty;
   std::swap( q, empty );
}
bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}
template<typename T>
int  GetDigit(T num){
    int digit=0;
    while(num!=0){
        num /= 10;
        digit++;
    }
    return digit;
}

template<typename T>
std::vector<T> enum_div(T n)//nの約数を列挙
{
	std::vector<T> ret;
	for(T i=1 ; i*i<=n ; ++i)
	{
		if(n%i == 0)
		{
			ret.push_back(i);
			if(i!=1 && i*i!=n)
			{
				ret.push_back(n/i);
			}
		}
	}
	return ret;
}


class DisjointSet{
    public:
        vector<int> rank, p;

        DisjointSet(){
        }

        DisjointSet(int size){
            rank.resize(size, 0);
            p.resize(size, 0);
            for (int i = 0; i < size;i++){
                makeSet(i);
            }
        }
        void makeSet(int x){
            p[x] = x;
            rank[x] = 0;
        }

        bool same(int x,int y){
            return findSet(x) == findSet(y);
        }
        void unite(int x,int y){
            link(findSet(x), findSet(y));
        }
        void link(int x,int y){
            if(rank[x]>rank[y]){
                p[y] = x;
            }else{
                p[x] = y;
                if(rank[x]==rank[y]){
                    rank[y]++;
                }
            }
        }
        int findSet(int x){
            if(x!=p[x]){
                p[x] = findSet(p[x]);
            }
            return p[x];
        }
};


int main()
{
    string s;
    cin >> s;
    int N = s.size();
    int p = 0;
    REP(i,0,N){
        if(s[i]=='p'){
            p++;
        }
    }

    cout << N / 2 - p << endl;
}

Measured memory_bytes: 512
<?php
$N = trim(fgets(STDIN));
$S = [];
$resultArr = [];

for ($i = 0; $i < $N; $i++) {
    $count = array_count_values(str_split(trim(fgets(STDIN))));
    if ($i == 0) {
        $resultArr = $count;
    } else {
        foreach ($resultArr as $key => $cnt) {
            if (isset($count[$key])) {
                $resultArr[$key] = min($resultArr[$key], $count[$key]);
            } else {
                $resultArr[$key] = 0;
            }
        }
    }
}

ksort($resultArr);

foreach ($resultArr as $key => $count) {
    echo(str_repeat($key, $count));
}

Measured memory_bytes: 4728
def readinput():
    x,y=list(map(int,input().split()))
    return x,y

def main(x,y):
    if(y%2==1):
        return 'No'
    ymin=2*x
    ymax=4*x
    if (ymin<=y) and (y<=ymax):
        return 'Yes'
    else:
        return 'No'

if __name__=='__main__':
    x,y=readinput()
    ans=main(x,y)
    print(ans)


Measured memory_bytes: 9212
#include<iostream>
#include<string>
using namespace std;
int main(){
	int w,h,x,y,r;
	cin>>w>>h>>x>>y>>r;
	if(0<=x-r&&0<=y-r&&w>=x+r&&h>=y+r)
		cout<<"Yes"<<endl;
	else
		cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 1156
S = int(input())
a = S // 1000
b = S // 100 - 10 * a
c = S // 10 - 100 * a - 10 * b
d = S - 1000 * a - 100 * b - 10 * c
if a == b or b == c or c == d:
    print("Bad")
else:
    print("Good")


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

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

  int n;cin>>n;
  std::vector<int> v(n);
  for(int i=0;i<n;i++){
    cin>>v[i];
  }
  int ans = v[0];
  for(int i=1;i<n;i++){
    ans = __gcd(ans, v[i]);
  }
  cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 640
# A - Darker and Darker
from collections import deque

H,W = map(int,input().split())
B = [[-1] * W for _ in range(H)]

queue = deque([])

for i in range(H):
    A = input()
    for j in range(W):
        if A[j]=='#':
            B[i][j] = 0
            queue.append((i,j))

ans = 0

while queue:
    I,J = queue.popleft()
    for di,dj in ((-1,0),(1,0),(0,-1),(0,1)):
        i,j = I+di,J+dj
        if 0<=i<H and 0<=j<W:
            if B[i][j]<0:
                B[i][j] = B[I][J]+1
                ans = max(ans,B[i][j])
                queue.append((i,j))

print(ans)

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

int main(){
  int a;
  cin >>a;
  bool expo[a+1];
  int p;
  for(int i=0;i<=a;i++) expo[i]=false;
  expo[1]=true;
  for(int i=2;i<=sqrt(a)+2;i++){
    for(int j=2;j<10;j++){
      p = pow(i,j);
      if(p<=a){
        expo[p] = true;
        continue;
      }
      break;
    }
  }
  for(int i=a;i>0;i--){
    if(expo[i]){
      cout << i<<endl;
      return 0;
    }
  }
}

Measured memory_bytes: 256
import qualified Data.ByteString.Char8 as C

main :: IO ()
main = do
  [a,b] <- map read . words <$> getLine
  print $ numOfPlndrm a b

numOfPlndrm
  :: Int -> Int -> Int
numOfPlndrm a b = length [x | x <- [a .. b], isP x]

isP 
  :: Int -> Bool
isP n = c == C.reverse c
  where
    c = C.pack $ show n

Measured memory_bytes: 1020
#include <iostream>
using namespace std;
int main(){
     int time[3],min=300;
     cin >> time[0] >> time[1] >>time[2];
     for (int i=0;i<3;i++){
          for (int j=0;j<3;j++){
               if (i!=j and min >= time[i]+time[j])min = time[i]+time[j];
          }
     }
     cout <<min<<endl;
}


Measured memory_bytes: 3608
#include <iostream>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main(){
	vector<long> S1, ans;
	vector<pair<long, long> > S2;
	char ch;
	long sum = 0;
	for (long i = 0; cin >> ch; i++){
		if (ch == '\\') S1.insert(S1.begin(), i);
		else if (ch == '/' && S1.size() > 0){
			long a = i - S1[0];
			sum += a;
			while (S2.size() > 0 && S2[0].first > S1[0]){
				a += S2[0].second; S2.erase(S2.begin());
			}
			S2.insert(S2.begin(), make_pair(S1[0], a));
			S1.erase(S1.begin());
		}
	}
	cout << sum << endl << S2.size();
	while (S2.size() > 0){cout << " " << S2[S2.size()-1].second; S2.erase(S2.end());}
	cout << endl;
	return 0;
}

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

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
  }
  sort(A.begin(), A.end());
  double p = A.at(0);
  for (int i = 0; i < N; i++) {
    p = (p + A.at(i))/2;
  }
  cout << p << endl;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;
public class Main
{
	public static void main(String args[])throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int arr[] = new int[5];
		for(int i=0;i<5;i++)
			arr[i] = Integer.parseInt(st.nextToken());
		for(int i=0;i<5;i++)
		{
			if(arr[i]==0){
				System.out.println(i+1);
				break;
			}
		}
	}
}

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

int main(void) {
    int N;
    string s;
    int64_t ans = 0;
    cin >> N;

    map<char,int64_t> mp;
    for(int i=0;i<N;i++) {
        cin >> s;
        switch(s[0]) {
            case 'M':
            case 'A':
            case 'R':
            case 'C':
            case 'H':
                mp[s[0]]++;
        }
    }

    if(mp.size() < 3) {
        cout << "0\n";
        return 0;
    }
    // 5 C 3 = 10 通りを全部ためす
    
    map<char,int64_t>::iterator i,j,k,iend,jend;
    jend = mp.end();
    jend--;
    iend = jend;
    iend--;
    for(i=mp.begin();i!=iend;i++) {
        j=i;j++;
        for(;j!=jend;j++) {
            k=j;k++;
            for(;k!=mp.end();k++) {
                ans += ((i->second) * (j->second) * (k->second));
            }
        }
    }

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


Measured memory_bytes: 256
// Problem F

#include <stdio.h>
#include <iostream>
#include <vector>
#include <string.h>
#include <cassert>
#include <algorithm>
#include <set>
#include <map>
#include <math.h>
#include <queue>
#include <stack>

#define MAXN 3005
#define pb push_back
#define mp make_pair
#define MOD 998244353 

using namespace std;

typedef long long int ll;
typedef pair<int, int> ii;

int N, S, A[MAXN];
int b[MAXN][MAXN];
ll pow2[MAXN];

ll f(int k, int s) {
  if (s<0) return 0;
  if (k == 0 && s!=0) return 0;
  if (b[k][s] != -1) return b[k][s];
  b[k][s] = ((ll)2*(ll)f(k-1,s))%MOD;
  b[k][s] = (b[k][s] + (ll)f(k-1, s-A[k-1]))%MOD; 
  return b[k][s];
}

int main() {
  cin >> N >> S;
  for (int i=0; i<N; i++) cin >> A[i];
  for (int i=0; i<MAXN; i++)
    for (int j=0; j<MAXN; j++)
      b[i][j] = -1;
  b[0][0] = 1;
  
  
  cout << f(N, S) << endl;
  
  
  return 0;
}


Measured memory_bytes: 39108
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

	int mod = 1000000007;

	static public int diff(int[] a, int i, int j) {
		return Math.abs(a[i] - a[j]);
	}

	public static void main(String[] args) {
		MyScanner sc = new MyScanner();
		out = new PrintWriter(new BufferedOutputStream(System.out));

		int n = sc.nextInt();

		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
		}

		//min cost to get here
		int prevPrev = 0;
		int prev = diff(a, 0, 1);

		for (int i = 2; i < n; i++) {
			int tmp = Math.min(prev + diff(a, i, i - 1), prevPrev + diff(a, i, i - 2));
			prevPrev = prev;
			prev = tmp;
		}
		
		out.println(prev);
		
		/*
		 * int n = sc.nextInt(); // read input as integer long k = sc.nextLong(); //
		 * read input as long double d = sc.nextDouble(); // read input as double String
		 * str = sc.next(); // read input as String String s = sc.nextLine(); // read
		 * whole line as String
		 * 
		 * int result = 3*n; out.println(result); // print via PrintWriter
		 */

		// Stop writing your solution here. -------------------------------------
		out.close();
	}

	// -----------PrintWriter for faster output---------------------------------
	public static PrintWriter out;

	// -----------MyScanner class for faster input----------
	public static class MyScanner {
		BufferedReader br;
		StringTokenizer st;

		public MyScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}

	}
	// --------------------------------------------------------
}


Measured memory_bytes: 42772
s = input()
#word = []
#for i in range(len(s)):
#    word.append(int(s[i]))
interval = len(s) - 1
ans = 0
for i in range(2**interval):
    f = list(s)
    for j in range(interval):
        if (i & (1<<j)):
            f[j] = f[j] + '+'
    f = "".join(f)
    #print(f)
    if '+' in f:
        #print(f.split('+'))
        ans = ans + sum(list(map(int,f.split('+'))))
    else:
        ans = ans + int(f)
print(ans)

Measured memory_bytes: 9000
#include <bits/stdc++.h>
using namespace std;
using sint = int64_t;

template<class T> T read() {
	T t;
	cin >> t;
	return t;
}

template<class T> vector<T> read_vector(sint const n) {
	vector<T> vs;
	for (sint i = 0; i < n; ++i) {
		vs.push_back(read<T>());
	}
	return vs;
}

inline void write() {
}

template<class T> void write(T const& t) {
	cout << t;
}

template<class T> void write(vector<T> const& ts) {
	if (ts.size() > 0) {
		cout << ts[0];
	}
	for (size_t i = 1; i < ts.size(); ++i) {
		cout << ' ' << ts[i];
	}
}

template<class T, class... Args> void write(T const& t, Args const&... args) {
	cout << t << ' ';
	write(args...);
}

template<class... Args> void writeln(Args const&... args) {
	write(args...);
	cout << '\n';
}

inline sint gcd(sint y, sint x) {
	while (x != 0) {
		sint const t = y % x;
		y = x;
		x = t;
	}
	return y;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin .exceptions(ios_base::badbit | ios_base::failbit);
	cout.exceptions(ios_base::badbit | ios_base::failbit);
	cin .tie(nullptr);
	cout.tie(nullptr);
	cout.precision(16);
	void run();
	run();
	return 0;
}

void run() {
	auto const N = read<sint>();

	vector<tuple<string, sint>> data;
	for (sint i = 0; i < N; ++i) {
		auto s = read<string>();
		auto t = read<sint>();
		data.push_back(make_tuple(s, t));
	}
	auto X = read<string>();

	sint i = 0;
	while (get<0>(data[i]) != X) {
		++i;
	}
	++i;
	sint t = 0;
	while (i < N) {
		t += get<1>(data[i]);
		++i;
	}
	writeln(t);
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>

using namespace std;

using ll = long long;

template <class T>
using grid = vector<vector<T>>;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)

#define input(...) __VA_ARGS__; in(__VA_ARGS__)

void print() {
  std::cout << std::endl;
}

template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
  std::cout << head << " ";
  print(std::forward<Tail>(tail)...);
}

void in() { }

template <class Head, class... Tail>
void in(Head&& head, Tail&&... tail) {
  cin >> head;
  in(std::forward<Tail>(tail)...);
}

int main() {
  ll input(n);
  string input(s);
  vector<ll> si(n);
  REP(i, n) si[i] = s[i] - '0';

  int ans = 0;
  REP(i, 10) REP(j, 10) REP(k, 10) {
    int number = i * 100 + j * 10 + k;
    // int number = i + j * 10 + k * 100;
    int cnt = 0;
    for (auto v: si) {
      if (number % 10 == v) {
        number /= 10;
        cnt++;
      }
      if (cnt == 3) {
        ans++;
        break;
      }
    }
  }
  print(ans);
}


Measured memory_bytes: 512
#include <stdio.h>
#include <string.h>
int main(){
char a[101],b[101],c[101],m,n;
scanf ("%s %s %s",&a,&b,&c);
m=strlen(a);
n=strlen(b);
if(a[m-1]==b[0]&&b[n-1]==c[0]){
	printf("YES");
}
else{
	printf("NO");
}
return 0;
}

Measured memory_bytes: 1728
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <stack>
#include <memory.h>
#include <list>
#include <numeric>
#include <functional>
#include <complex>
#include <cassert>
#include <regex>
#include <random>

#define ll long long
#define ld long double
#define ull unsigned ll
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pii pair<int,int> 
#define vi vector<int>
#define vpii vector<pii>
#define vvi vector<vector<int>>
#define forn(it,from,to) for(int (it)=from; (it)<to; (it)++)
const int  Inf = 2 * 1000 * 1000 * 1000;
ll LINF = (ll)4e18;
using namespace std;
#define M_PI       3.14159265358979323846   // pi

const int nax = 1e5 + 5;

int D[nax];
int deg[nax];

vector<int>g[nax];
int used[nax];

void dfs(int v) {
	used[v] = 1;

	for (auto to : g[v]) {
		D[to] = max(D[to], D[v] + 1);
		deg[to]--;
		if (deg[to] == 0) dfs(to);
	}
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#else
	//freopen("sum.in", "r", stdin);
	//freopen("sum.out", "w", stdout);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		g[a].emplace_back(b);
		deg[b]++;
	}

	for (int i = 1; i <= n; i++) {
		if (deg[i] == 0 && !used[i]) {
			dfs(i);
		}
	}
	int mx = 0;
	
	for (int i = 1; i <= n; i++) {
		mx = max(mx, D[i]);
	}
	cout << mx;
 	return 0;
}

Measured memory_bytes: 9984
#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
using namespace std;

int main(){
  int result = 0;
  string s;

  cin >> s;
  if (s[0] == '1') result++;
  if (s[1] == '1') result++;
  if (s[2] == '1') result++;
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using uint = unsigned int;
using P = pair<int,int>;
using node = pair<string,ll>;
const ll inf = numeric_limits<ll>::max()/3;
const ll mod = 1e9+7;

vector< ll > ls;
vector< ll > abc;
vector< vector<int> > comb;

ll dfs(int idx) {
  if(idx == (int)ls.size()) {
    ll res = 0LL;
    for(int i = 0;i < 3;++i){
      if(comb[i].empty()) {
        return inf;
      }
      ll calc = 0LL;
      for(int j = 0;j < comb[i].size();++j) {
        calc += comb[i][j];
      }
      res += (comb[i].size() - 1) * 10;
      res += (ll)abs(calc - abc[i]);
    }
    return res;
  }
  ll res = inf;
  for(int i = 0;i < 4;++i){
    comb[i].push_back(ls[idx]);
    res = min(res, dfs(idx+1));
    comb[i].pop_back();
  }
  return res;
}

int main(void) {
  ls.clear();abc.clear();comb.clear();
  abc.resize(4);comb.resize(4);
  ll n;
  cin >> n >> abc[0] >> abc[1] >> abc[2];
  ls.resize(n);
  for(int i = 0;i < n;++i) {
    cin >> ls[i];
  }
  cout << dfs(0) << endl;
  return 0;
}


Measured memory_bytes: 256
from sys import stdin
import math
import fractions
from collections import deque

INF = 10 ** 10

N, M = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]
BC = [list(map(int, stdin.readline().rstrip().split())) for _ in range(M)]
A.sort()
BC.sort(key=lambda x: (x[1]), reverse=True)

i = 0
A_len = len(A)

for B, C in BC: # O(10^5)
    for _ in range(B):
        if A[i] < C:
            A[i] = C
            i += 1
            if i > A_len - 1:
                print(sum(A))
                exit()
        else:
            print(sum(A))
            exit()

print(sum(A))

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

int main()
{
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i = 0;i < n;i++) cin >> a[i];
  sort(a.begin(),a.end());
  cout << a[n-1] - a[0] << endl;

}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(int argc, char* argv[])
{
  int N; cin >> N;

  unsigned int val; cin >> val;
  for (int i = 1; i < N; i++) {
    unsigned int a; cin >> a;
    val ^= a;
  }

  cout << (val != 0 ? "No" : "Yes") << 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++)
typedef long long ll;
#define dump(x) cerr<<#x<<"="<<x<<endl
using P = pair<int, int>;

int main() {
   int n; cin >> n;
   vector<ll> a(n+1, 0);
   for(int i=1; i<n+1; i++){
      cin >> a.at(i);
   }

   map<ll, ll> b, c;
   for(int i=1; i<=n; i++){
      b[a.at(i)+i]++;
      if(i-a.at(i)>0) c[i-a.at(i)]++;
   }

   ll cnt = 0;
   for(auto x:b){
      ll tmp = c[x.first]; 
      cnt += tmp * x.second;
   }

   cout << cnt << endl;

   return 0;
}


Measured memory_bytes: 29968
N = int(input())
 
R = [int(input()) for i in range(N)]
 
maxv = -2000000000
minv = R[0]
 
for i in range(1,N):
    maxv = max(maxv, R[i] - minv)
    minv = min(minv, R[i])
 
print(maxv)


Measured memory_bytes: 13592
// Course＞Introduction to Programming I ＞ ITP1_1_C:   Rectangle
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_C&lang=jp

// 以下のソースコードには(複数の？)誤りがあるので、このまま提出しても「誤り」と判定されます。
// ソースコード中の誤りを修正し、「正解」（Accepted）を出してください。

// 適宜、paiza.io (https://paiza.io/ja/projects/new) などのC++実行環境を、確認に用いることを推奨します。


#include <iostream>
using namespace std;

int main(){
	int a,b;
	cin >> a >> b;
	cout << (a*b) << " "<< (a+b)*2 << endl;
	return 0;
}


Measured memory_bytes: 3072
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>

// Acknowledgement: Special thanks to kyomukyomupurin, who developed this
// template.
template <class T, class U>
std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p) {
  return os << '(' << p.first << ", " << p.second << ')';
}

template <class T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) {
  int n = 0;
  for (auto e : vec) os << (n++ ? ", " : "{") << e;
  return os << (n ? "}" : "{}");
}

template <class T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& st) {
  int n = 0;
  for (auto e : st) os << (n++ ? ", " : "{") << e;
  return os << (n ? "}" : "{}");
}

template <class T, class U>
std::ostream& operator<<(std::ostream& os, const std::map<T, U>& mp) {
  int n = 0;
  for (auto e : mp) os << (n++ ? ", " : "{") << e;
  return os << (n ? "}" : "{}");
}

template <class T>
std::istream& operator>>(std::istream& is, std::vector<T>& vec) {
  for (T& e : vec) is >> e;
  return is;
}

#ifdef LOCAL
#define debug(...) \
  std::cerr << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

void debug_out() { std::cerr << '\n'; }

template <class Head, class... Tail>
void debug_out(Head&& head, Tail&&... tail) {
  std::cerr << head;
  if (sizeof...(Tail) != 0) std::cerr << ", ";
  debug_out(std::forward<Tail>(tail)...);
}
using namespace std;
using int64 = long long;

int main() {
  int N, M;
  cin >> N >> M;
  vector<int64> A(N);
  cin >> A;
  priority_queue<int64> pq;
  for (int i = 0; i < N; i++) {
    pq.push(A[i]);
  }
  for (int i = 0; i < M; i++) {
    int64 mx = pq.top();
    pq.pop();
    pq.push(mx / 2);
  }
  int64 ans = 0;
  while (pq.size() > 0) {
    ans += pq.top();
    pq.pop();
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 4988
n, m, k = map(int, input().split())
a_i = [int(x) for x in input().split()]
b_i = [int(x) for x in input().split()]

csum_a = [0]
csum_b = [0]

for i in range(n):
    csum_a.append(csum_a[i] + a_i[i])
    
for i in range(m):
    csum_b.append(csum_b[i] + b_i[i])
    
b_num = m + 1
ans = 0

for i in range(n + 1):
    for j in reversed(range(b_num)):
        if csum_a[i] + csum_b[j] <= k:
            ans = max(ans, i + j)
            b_num = j + 1
            break

print(ans)

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

using namespace std;
const int mod = 1e9+7;
int add(int a, int b) {
	return a + b >= mod ? a + b - mod : a + b;
}
int mul(int a, int b) {
	return int(1LL * a * b % mod);
}
const int N = 100005;

int n;
char s[N];
int pot[N];

int dp[N][2][2];
int f(int i, int less, int dif) {
	if(i == n) return 1;
	int &ans = dp[i][less][dif];
	if(~ans) return ans;
	ans = 0;
	if(less) {
		ans = add(ans, f(i + 1, 1, dif));
		ans = add(ans, f(i + 1, 1, 1));
		ans = add(ans, f(i + 1, 1, 1));
	}
	else {
		if(s[i] == '0') {
			ans = f(i + 1, 0, dif);
		}
		else {
			ans = f(i + 1, 1, dif);
			ans = add(ans, f(i + 1, 0, 0));
			if(dif) {
				ans = add(ans, f(i + 1, 1, 1));
			}
			else {
				ans = add(ans, f(i + 1, 0, 0));
			}
		}
	}
	return ans;
}

int main() {
	memset(dp, -1, sizeof dp);
	pot[0] = 1;
	scanf("%s", s);
	n = (int)strlen(s);

	printf("%d\n", f(0, 0, 0));

	int ans = 0;

	for(int i = 0; i < n; i++) {
		if(s[i] == '1') {

		}
	}
}


Measured memory_bytes: 6656
#include "bits/stdc++.h"
using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP0(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REP1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)

typedef long long LL;
typedef pair<int, int> pii;

const int INTINF = 1e9;
const LL LLINF = 1e18;

LL digit10(LL N)
{
    LL ans = 0;
    while (N)
    {
        ans++;
        N /= 10;
    }
    return ans;
}

void solve()
{
    LL N;
    cin >> N;
    // 最大は 1*N のときのNの桁数
    LL ans = (N % 2 == 0 ? digit10(N / 2) : digit10(N));

    for (LL i = 3; i * i <= N; i += 2)
    {
        if (N % i == 0)
            ans = digit10(N / i);
    }
    cout << ans << endl;
}

int main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(10);
    solve();
    return 0;
}

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

string S,T;
int SS[101010],TS[101010];
int Q;
int A,B,C,D;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S>>T>>Q;
	FOR(i,S.size()) SS[i+1]=SS[i]+(S[i]-'A')+1;
	FOR(i,T.size()) TS[i+1]=TS[i]+(T[i]-'A')+1;
	
	while(Q--) {
		cin>>A>>B>>C>>D;
		
		if((SS[B]-SS[A-1])%3==(TS[D]-TS[C-1])%3) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n';
	FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	solve(); return 0;
}


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

int main() {
    int h, w;
    cin >> h >> w;
    string grid[h];
    int row_light[h][w] = {0};
    int column_light[h][w] = {0};
    int total_light[h][w] = {0};
    rep(i,h) {
        cin >> grid[i];       
    }
    rep(i,h) {
        int light = 0;
        rep(j,w) {
            if (grid[i][j] == '#') {
                row_light[i][j] = 0;
                light = 0;
            }
            else {
                light++;
                row_light[i][j] = light;
            }
        }
        light = 0;
        bool combo = false;
        rep(j,w) {
            if (row_light[i][w-j-1] > 0 && combo) {
                row_light[i][w-j-1] = light;
            }
            if (row_light[i][w-j-1] > 0 && !combo) {
                light = row_light[i][w-j-1];
                combo = true;
            }
            if (row_light[i][w-j-1] == 0) {
                combo = false;
            }
        }
    }
    rep(j,w) {
        int light = 0;
        rep(i,h) {
            if (grid[i][j] == '#') {
                column_light[i][j] = 0;
                light = 0;
            }
            else {
                light++;
                column_light[i][j] = light;
            }
        }
        light = 0;
        bool combo = false;
        rep(i,h) {
            if (column_light[h-i-1][j] > 0 && combo) {
                column_light[h-i-1][j] = light;
            }
            if (column_light[h-i-1][j] > 0 && !combo) {
                light = column_light[h-i-1][j];
                combo = true;
            }
            if (column_light[h-i-1][j] == 0) {
                combo = false;
            }
        }
    }
    int max_light = 0;
    rep(i,h) {
        rep(j,w) {
            total_light[i][j] = row_light[i][j] + column_light[i][j];
            max_light = max(total_light[i][j], max_light);
        }
    }
    cout << max_light - 1<< endl;
}   

Measured memory_bytes: 51200
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &vec){ os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const deque<T> &vec){ os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa){ os << "(" << pa.first << "," << pa.second << ")"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template<typename T> void ndarray(vector<T> &vec, int len) { vec.resize(len); }
template<typename T, typename... Args> void ndarray(vector<T> &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) ndarray(v, args...); }
template<typename T> void Max(T &m, const T q) { if (m < q) m = q; }
template<typename T> void Min(T &m, const T q) { if (m > q) m = q; }
template<typename T1, typename T2> pair<T1, T2> operator+(pair<T1, T2> &l, pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }
template<typename T1, typename T2> pair<T1, T2> operator-(pair<T1, T2> &l, pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); }
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;

int N;
vector<vector<int>> a;

int main()
{
    cin >> N;
    ndarray(a, N, 3);
    cin >> a;
    vector<vector<int>> dp;
    ndarray(dp, N + 1, 3);
    REP(i, N) REP(j, 3) REP(k, 3) if (j != k) Max(dp[i + 1][j], dp[i][k] + a[i][j]);

    cout << *max_element(dp.back().begin(), dp.back().end()) << endl;
}


Measured memory_bytes: 11264
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <vector>
#include <algorithm>
#include <map>

int main(){
  long long N;
  scanf("%lld\n", &N);
  std::vector<long long >a(N+5);
  long long temp;
  for (long long i=0; i<N; i++){
    scanf("%lld", &temp);
    temp--;
    a[i] = temp;
  }
  //printf("read end\n");
  long long counter = 0;
  long long iterator = 0;
  long long breaknum = 0;
  while(iterator<N){
    //printf("check a[%lld](=%lld) != %lld\n",iterator, a[iterator], counter);
    while (a[iterator]!=counter){
      breaknum++;
      iterator++;
      if (iterator>=N && counter>0){
        printf("%lld\n", breaknum);
        return 0;
      } else if (iterator>=N && counter==0){
        printf("-1\n");
        return 0;
      }
    }
    counter++;
    iterator++;
    /*if (iterator>=N){
      printf("-1\n");
      return 0;
      }*/
  }
  printf("%lld\n", breaknum);
  return 0;
}


Measured memory_bytes: 1792
import sys
readline = sys.stdin.readline
N,S = map(int,readline().split())
A = list(map(int,readline().split()))
dp = [[0]*(S+2) for i in range(N+1)]
dp[0][0] = 1
mod = 998244353
for i,a in enumerate(A):
    for j in range(S+1):
        if j-a >= 0:
            dp[i+1][j] = (dp[i][j]*2+dp[i][j-a])%mod
        else:
            dp[i+1][j] = dp[i][j]*2%mod
print(dp[N][S])


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

using namespace std;

int cnth[1500001], cntw[1500001];

int main()
{
  int N, M;
  while(cin >> N >> M, N || M){
    int h[2048], w[2048], hh[2048], ww[2048];
    hh[0] = 0; ww[0] = 0;
    for(int i = 0; i < N; i++) cin >> h[i], hh[i+1] = hh[i] + h[i];
    for(int i = 0; i < M; i++) cin >> w[i], ww[i+1] = ww[i] + w[i];
    memset(cnth, 0, sizeof(cnth));
    memset(cntw, 0, sizeof(cntw));
    for(int i = 0; i < N; i++){
      for(int j = i+1; j < N+1; j++) cnth[hh[j]-hh[i]]++;
    }
    for(int i = 0; i < M; i++){
      for(int j = i+1; j < M+1; j++) cntw[ww[j]-ww[i]]++;
    }
    int ans = 0;
    for(int i = 1; i <= 1500000; i++) ans += cnth[i] * cntw[i];
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 12920
#include<iostream>
#include<algorithm>
#include<map>
using lint=int64_t;
using namespace std;

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

	map<pair<lint,lint>,lint> m;
	for(lint i=0;i<N;i++)
	{
		lint a,b;
		cin >> a >> b;
		for(lint y=a-2;y<=a;y++)
		{
			for(lint x=b-2;x<=b;x++)
			{
				if(y<1 || x<1 || y+2>H || x+2>W)
					continue;
				m[make_pair(y,x)]++;
			}
		}
	}
	
	lint ans[10]={};
	lint cnt=0;
	for(auto&& i:m)
	{
		cnt++;
		ans[i.second]++;
	}
	ans[0]=(H-2)*(W-2)-cnt;
    
	for(lint i=0;i<10;i++)
		cout << ans[i] << endl;
	return 0;
}


Measured memory_bytes: 56448
#include <stdio.h>
#include <stdlib.h>

#define MAX 2000001
#define VMAX 10000

int main(void)
{
	unsigned short *A, *B;
	
	int C[VMAX+1];
	int n, i, j;
	scanf("%d",&n);
	
	A = malloc(sizeof(short)*n+1);
	B = malloc(sizeof(short)*n+1);
	
	for(i=0;i<=VMAX;i++) C[i] = 0;
	
	for(i=0;i<n;i++) {
		scanf("%hu",&A[i+1]);
		C[A[i+1]]++;
	}
	
	for(i=1;i<=VMAX;i++) C[i] = C[i] + C[i-1];
	
	for(j=n;j>=1;j--) {
		B[C[A[j]]] = A[j];
		C[A[j]]--;
	}
	
	for(i=1;i<=n;i++) {
		if(i>1) printf(" ");
		printf("%d",B[i]);
	}
	printf("\n");
	
	return 0;
}



Measured memory_bytes: 9584
#include <bits/stdc++.h>
//#include "Local_Debug.h"
using namespace std;
#define Endl endl
#define debug(x) cout << #x << " = " << (x) << endl
typedef long long ll;
const int MOD = (int)1e9 + 7;
const int MAXN = (int)2e5 + 5;
ll a, b, c;
int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	while (cin >> a >> b >> c)
	{
		cout << (a + b + c >= 22 ? "bust" : "win") << endl;
	}
}
/*
5 7 9

13 7 2
*/

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<stdlib.h>
#include<utility>
#include<functional>
#include<cfenv>
#include<cmath>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<set>

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define vint vector<int>
#define vvint vector<vint>
#define P pair<ll,ll>
#define INT_MAX 2147483647
#define MOD 1000000007
#define PI 3.14159265358979323846
#define all(a) (a).begin(),(a).end()
using namespace std;
typedef long long ll;

#define MAX 1000000000000


int main(void) {
	int x, y; cin >> x >> y;
	
	if ((y - 2 * x) % 2 == 0 && y - 2 * x >= 0) {
		if ((4 * x - y) % 2 == 0 && 4 * x - y >= 0) {
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
#define ll long long

ll gcd(int a,int b)
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);
}
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int k;
    cin>>k;
    ll sum=0;
    for(int i=1;i<=k;i++)
    {
        for(int j=1;j<=k;j++)
        {
            for(int l=1;l<=k;l++)
                sum+=gcd(i,gcd(j,l));
        }
    }
    cout<<sum;
}

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

int main() {
    int N;
    cin>>N;
    vector<int> a(N);
    int sum=0;


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

    int mini = sum;
    int prefix_sum = 0;
    for(int i=0;i<N;i++){
        cin>>a[i];
        prefix_sum += a[i];
        mini = min(mini, abs(prefix_sum-(sum-prefix_sum)));
    }
    cout << mini << endl;

    return 0;
}

Measured memory_bytes: 256