akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())
#define endl "\n"
template<class T> void chmax(T &a, const T b){ a = max(a, b); }
template<class T> void chmin(T &a, const T b){ a = min(a, b); }

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // ifstream in("input.txt");
    // cin.rdbuf(in.rdbuf());
    ll n ,x, t;
    cin >> n >> x >> t;
    cout << ((n + (x - 1)) / x * t) << endl;
    return 0;
}


Measured memory_bytes: 3644
//
// Created by yamunaku on 2019/10/15.
//

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repl(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perl(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD9 998244353
#define MOD1 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)
#define CST(x) cout<<fixed<<setprecision(x)

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int>> mti;
typedef vector<ll> vl;
typedef vector<vector<ll>> mtl;

struct node{
    ll kou;
    ll num;
};

int main(){
    int h, w;
    ll m;
    cin >> h >> w >> m;
    vector<string> f(h);
    rep(i, h) cin >> f[i];
    ll ans = 0;
    vector<vector<node>> dp(h + 1, vector<node>(w + 1, {0, 0}));
    vector<vector<ll>> dp2(h + 1, vl(w + 1, 0));
    dp2[0][1] = 1;
    rep(i,h){
        rep(j,w){
            dp2[i+1][j+1] = (dp2[i+1][j]+dp2[i][j+1])%m;
        }
    }
    dp[0][1] = {0, 1};
    rep(i, h){
        rep(j, w){
            dp2[i + 1][j + 1] = (dp2[i + 1][j] + dp2[i][j + 1]) % m;
            dp[i + 1][j + 1] = {(dp[i][j + 1].kou + dp[i + 1][j].kou) % m,
                                (dp[i][j + 1].num + dp[i + 1][j].num) % m};
            if(f[i][j] == '+'){
                ans = (ans + dp[i + 1][j + 1].kou*dp2[h-i][w-j]) % m;
                dp[i + 1][j + 1] = {0, dp2[i+1][j+1]};
            }else if(f[i][j] == '*'){
                dp[i + 1][j + 1].num = dp[i + 1][j + 1].kou;
                dp[i + 1][j + 1].kou = 0;
            }else{
                dp[i + 1][j + 1].kou = (dp[i + 1][j + 1].kou * 10 + (f[i][j] - '0') * dp[i + 1][j + 1].num) % m;
            }
        }
    }
    ans = (ans + dp[h][w].kou) % m;
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 96072
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        long m = in.nextLong();

        if (m <= 2 * n) {
            System.out.println(Math.min(n,  m / 2));
        } else {
            System.out.println(n + (m - 2 * n) / 4);
        }

    }
}


Measured memory_bytes: 20692
N,x = map(int,input().split())
a = list(map(int,input().split()))
A = sorted(a)

cont = 0
if x > sum(A):
    print(N-1)
else:
    for i in range(N):
        if x >= A[i]:
            x -= A[i]
            cont += 1
    print(cont)

Measured memory_bytes: 9192
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long
using namespace std;

int powmod(int a, int n, int mod) {
	if (n == 0) return 1;
	if (n % 2 == 0) return powmod((a * a) % mod, n / 2, mod);
	return (a * powmod(a, n - 1, mod)) % mod;
}

int mod = 1000000007;
int n, k;

signed main() {
	cin >> n >> k;
	
	int x;
	static int w[100001] = {0};
	for (x = 1; x <= k; x++) {
		w[x] = powmod(k / x, n, mod);
	}
	
	static int a[100001] = {0};
	int ans = 0;
	for (x = k; x >= 1; x--) {
		a[x] = w[x];
		for (int y = 2 * x; y <= k; y += x) {
			a[x] = (a[x] + mod - a[y]) % mod;
		}
		ans += x * a[x];
		ans %= mod;
	}
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 5140
#include <iostream>
#include <map>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <climits>
#include <stack>
#include <queue>
#include <set>
#include <cctype>
#include <bitset>
#include <type_traits>

#include <list>
using namespace std;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define YES(j) cout << (j ? "YES" : "NO") << endl;
#define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
#define yes(j) std::cout << (j ? "yes" : "no") << endl;

void move(int sx, int sy, int tx, int ty)
{
    char t;
    if (sx < tx)
    {
        t = 'R';
    }
    else
    {
        t = 'L';
    }
    REP(i, abs(tx - sx))
    {
        cout << t;
    }
    if (sy < ty)
    {
        t = 'U';
    }
    else
    {
        t = 'D';
    }
    REP(i, abs(ty - sy))
    {
        cout << t;
    }
}
int main(void)
{
    int sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;
    move(sx, sy, tx, ty);
    move(tx, ty, sx, sy);
    cout << "D";
    move(sx, sy - 1, tx + 1, ty);
    cout << "L";
    cout << "U";
    move(tx, ty + 1, sx - 1, sy);
    cout << "R" << endl;
}

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

// #define int long long
#define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i)
#define reps(i, n) for (long long i = (long long)(1); i <= (long long)(n); ++i)
#define rrep(i, n) for (long long i = ((long long)(n)-1); i >= 0; i--)
#define rreps(i, n) for (long long i = ((long long)(n)); i > 0; i--)
#define irep(i, m, n) for (long long i = (long long)(m); i < (long long)(n); ++i)
#define ireps(i, m, n) for (long long i = (long long)(m); i <= (long long)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) long long(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

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

const ll INF = 1e9;
const ll MOD = 1e9+7;
const ll LINF = 1e18;



signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  ll k,a,b; cin>>k>>a>>b;
  reps(i,1000){
    ll now=k*i;
    if(a<=now&&now<=b){
      cout<<"OK"<<endl;
      return 0;
    }
  }
  cout<<"NG"<<endl;
  return 0;
}

Measured memory_bytes: 3648
using System;
using System.Linq;
namespace aoj {
	public class Program {
		public static void Main() {
			string str;
			while ((str = Console.ReadLine()) != null) {
				var ns = str.Select(c=>int.Parse(c.ToString())).ToArray();
				for (int i = 0; i < 9; i++) {
					for (int j = 0; j < 9 - i; j++) {
						var nc = (ns[j] + ns[j + 1]).ToString();
						ns[j] = int.Parse(nc[nc.Length - 1].ToString());
					}
				}
				Console.WriteLine(ns[0]);
			}
		}
	}
}

Measured memory_bytes: 9512
"use strict";
    
const main = arg => {
    arg = arg.trim().split("\n");
    const N = parseInt(arg[0].split(" ")[0]);
    const A = arg[1].split(" ").map(n=>parseInt(n));
    
    let map = {};
    
    for(let i in A) {
        let plus = A[i] + 1;
        let raw = A[i];
        let minus = A[i] - 1;
    
        
        if(!map[plus]) {
            map[plus] = 1;
        } else {
            map[plus]++;
        }
        
        if(!map[raw]) {
            map[raw] = 1;
        } else {
            map[raw]++;
        }
        
        if(!map[minus]) {
            map[minus] = 1;
        } else {
            map[minus]++;
        }
    }
    
    let answer = 0;
    
    for(let key in map) {
        answer = Math.max(answer, map[key]);
    }
    
    // console.log(JSON.stringify(map));
    console.log(answer);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 37312
take_input = input().split(" ")
n = int(take_input[0])
x = int(take_input[1])
t = int(take_input[2])
con1 = n >= 1 and n <= 1000
con2 = x >= 1 and x <= 1000
con3 = t >= 1 and t <= 1000
temp = 0
time = 0
result = 0
if con1 == True and con2 == True and con3 == True:
    for i in range (1, 10000000000):
        temp = i * x
        if temp >= n:
            time = i
            break
        else:
            continue
    result = time * t
    print(result)
else:
    print()


Measured memory_bytes: 9200
m,d = gets.split.map(&:to_i)

count = 0
1.upto(m) do |mm|
  1.upto(d) do |dd|
    next if dd < 11
    d10,d1 = dd.to_s.split('')
    next if d10.to_i < 2 || d1.to_i < 2
    count += 1 if mm == d10.to_i * d1.to_i
  end
end

puts count

Measured memory_bytes: 4220
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<stack>
#include<set>
#include<map>
#include<utility>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;

typedef long long ll;
const int mod=1e9+7;

int main(){
	int n;
	cin >> n;
	vector<int> a(n+2);
	ll sum=0;
	for(int i=1; i<=n; i++){
		cin >> a[i];
		sum+=abs(a[i]-a[i-1]);
	}
	sum+=abs(a[n]);
	for(int i=1; i<=n; i++)
		cout << sum-abs(a[i]-a[i-1])-abs(a[i+1]-a[i])+abs(a[i+1]-a[i-1]) << endl;
	return 0;
}

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

int main(){
    int n,ans=0;
    int d;
    cin>>n>>d;
    for(int i=0;i<n;i++){
        int x,y;
        double dd;
        cin>>x>>y;
        int a=abs(x);
        int b=abs(y);
        // temp=a>b?a:b;
        long long m=pow(a,2);
        dd = sqrt(m);
        if(dd<=(double)d){
            m += pow(b,2);
            dd = sqrt(m);
            if(dd<=(double)d){
                ans++;
            }
        }
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 3664
#include<stdio.h>
int main(){
  int S = -1;
  int h,m,s;
  while(S<0 || 86400<S){
    scanf("%d",&S);
  }
  h = S/3600;
  m = (S - h*3600) / 60;
  s = S - h*3600 - m*60;
  printf("%d:%d:%d\n",h,m,s);
  return 0;
}

Measured memory_bytes: 592
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
double pi = acos(-1.0);
const double EPS=1e-9;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL)
#define t() ll t;cin>>t;while(t--) 

int main()
{ 
    fastio;
    ll i,n,j,k,w;
    cin>>n>>w;
    //dp[i][j]=till index i using atmost weight j
    vector<vector<ll>>dp(n,vector<ll>(w+1,-1));
    vector<ll>wei(n),val(n);
    for(i=0;i<n;i++) cin>>wei[i]>>val[i];
    //base case
    for(j=0;j<wei[0];j++) dp[0][j]=0;
    for( ; j<=w;j++) dp[0][j]=val[0];
    for(i=1;i<n;i++)
    {
        for(j=0;j<=w;j++)
        {
            if(j>=wei[i]) 
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-wei[i]]+val[i]);
            else 
                dp[i][j]=dp[i-1][j];
        }
    }
    cout<<dp[n-1][w];

    
       
}

Measured memory_bytes: 79488
S = str(input())
N = len(S)
sList = [str(s) for s in S]
isPalindrome = 1
str1 = ''
str2 = ''
str3 = ''
str4 = ''

for i in range(N):
  if (sList[i] != sList[N - 1 - i]):
    isPalindrome = 0
if isPalindrome == 1:
  for i in range(int((N - 1) / 2)):
    str1 += sList[i]
    str2 += sList[int((N - 1) / 2 - 1 - i)]
    str3 += sList[int((N + 3) / 2 - 1 + i)]
    str4 += sList[N - 1 - i]
    
    if str1 != str2:
      isPalindrome = 0
    if str3 != str4:
      isPalindrome = 0
if isPalindrome == 0:
  print('No')
else:
  print('Yes')

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

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef double ld;
//#define ll __int128
//#define int ll
//#define int ll
//#define char ll
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<vvc> vvvc;
typedef pair<int, int> pii;
typedef pair<pii, pii> piii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector< vi > vvi;
typedef vector< vvi > vvvi;
typedef vector<short> vs;
typedef vector<vs> vvs;
typedef vector<vvs> vvvs;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef vector<ld> vld;
typedef vector<vld> vvld;
typedef vector<vvld> vvvld;
typedef vector<string> vst;
typedef vector<vst> vvst;
typedef pair<ld, ld> pld;

#define inmin(a, b) a = min(a, (b))
#define inmax(a, b) a = max(a, (b))
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define sqr(x) ((x) * (x))
#define fori(i, n) for(int i = 0; i < (int)(n); ++i)
#define SZ(a) ((int)((a).size()))
#define triple(T) tuple<T, T, T>
#define quad(T) tuple<T, T, T, T>
#define watch(x) cerr << (#x) << " = " << (x) << endl;

#ifdef MAX_HOME
#define cerr cout
#else
#define cerr if (false) cerr
#endif

const double PI = 2 * acos(0.0);
#define rand shittttty_shit
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng_64(chrono::steady_clock::now().time_since_epoch().count());

const string DIGITS = "0123456789";
const string ALPH = "abcdefghijklmnopqrstuvwxyz";


template <class T0, class T1>
inline ostream & operator << (ostream &out, pair<T0, T1> &a) {
    return out << "{" << a.first << ", " << a.second << "}";
}

template <class T0, class T1>
inline istream & operator >> (istream &in, pair<T0, T1> &a) {
    return in >> a.first >> a.second;
}

template <class T0, class T1, class T2>
inline ostream & operator << (ostream &out, tuple<T0, T1, T2> &a) {
    return out << "{" << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << "}";
}

template <class T0, class T1, class T2, class T3>
inline ostream & operator << (ostream &out, tuple<T0, T1, T2, T3> &a) {
    return out << "{" << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << ", " <<  get<3>(a) << "}";
}

template<class T>
inline ostream & operator << (ostream &out, vector<T> &a) {
    out << "[";
    fori (i, a.size())
        out << a[i] << vector<string>{", ", "]  "}[i + 1 == a.size()];
    return out;
}


void smain();



signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
#ifdef MAX_HOME
    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    clock_t start = clock();
#endif
    cout << setprecision(4) << fixed;
    smain();
#ifdef MAX_HOME
    cout << "\n\n\n\nTOTAL EXECUTION TIME: " << float( clock () - start ) /  CLOCKS_PER_SEC << endl;
#endif
    return 0;

}

void smain() {
    int n;
    cin >> n;
    bool ok = true;
    fori (i, n) {
        int cur;
        cin >> cur;
        ok ^= cur & 1;
    }
    cout << (ok ? "YES\n" : "NO\n");
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>
#include<math.h>

typedef struct{
    int p;
    char s[3];
}kekka;

int p_comp(const void*a,const void*b){return ((kekka*)a)->p-((kekka*)b)->p;}

int int_comp(const void*a,const void*b){return *(int*)a-*(int*)b;}
int frag[100];
int num[100];
void fx(int n,int k)
{
    int f,i,j;
    for(i=0;i<n;i++){
        f=frag[i];
        if(f==0){
            frag[i]=1;
            num[n-k]=i+1;
            if(k==1){
                //num[]に数字が入ってる
            }
            else{
                fx(n,k-1);
            }
            frag[i]=0;
        }
    }
}

int main()
{
    int n,m;
    kekka list[100000];
    int frag[100000];

    scanf("%d %d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%d %s",&list[i].p,list[i].s);
    }
    for(int i=0;i<100000;i++){
        frag[i]=0;
    }
    //qsort(list,m,sizeof(kekka),p_comp);
    int accnt=0;
    int wacnt[100000];
    for(int i=0;i<100000;i++)wacnt[i]=0;

    for(int i=0;i<m;i++){
        if(!strcmp(list[i].s,"AC")){
            if(frag[list[i].p-1]==0){
                accnt++;
                frag[list[i].p-1]=1;
            }
        }
        else if(!strcmp(list[i].s,"WA")){
            if(frag[list[i].p-1]==0){
                wacnt[list[i].p-1]++;
            }
        }
    }
    int wasum=0;
    for(int i=0;i<n;i++){
        if(frag[i]==1){
            wasum+=wacnt[i];
        }
    }
    printf("%d %d\n",accnt,wasum);


    return 0;
}

Measured memory_bytes: 1664
tmp = list(map(int, input().split()))
w = tmp[0]
h = tmp[1]
x = tmp[2]
y = tmp[3]

area  = w * h / 2
if x == w / 2 and y == h / 2:
  judge = 1
else:
  judge = 0

print(str(area) + ' ' + str(judge))

Measured memory_bytes: 38256
package main

import (
	"fmt"
	"math"
	"math/big"
)

func main() {
	solve()
}

func solve() {
	var n int
	fmt.Scan(&n)
	c := 0
	p := make([]int, n)
	pmax := 100000000
	for i := 0; i < n; i++ {
		fmt.Scan(&p[i])
		if p[i] < pmax {
			pmax = p[i]
			c = c + 1
		}
	}
	fmt.Println(c)
}

func max(x int, y ...int) int {
	res := float64(x)
	for _, z := range y {
		res = math.Max(res, float64(z))
	}
	return int(res)
}

func min(x int, y ...int) int {
	res := float64(x)
	for _, z := range y {
		res = math.Min(res, float64(z))
	}
	return int(res)
}

func abs(x int) int {
	return int(math.Abs(float64(x)))
}

func sqrt(x int) int {
	return int(math.Sqrt(float64(x)))
}

func int2Int(x int) big.Int {
	var res big.Int
	res.SetInt64(int64(x))
	return res
}


Measured memory_bytes: 4992
#include<bits/stdc++.h>
/*
g++ -std=c++11 -Wall -g -fsanitize=undefined -D_GLIBCXX_DEBUG abc/abc076/c.cpp
*/
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define SZ(x) ((int)(x).size())
typedef long long ll;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);//おまじないでcin, cout早くする
    string S, T, ans;
    cin >> S;
    cin >> T;
    ans = S;
    
    int n, m;
    n = S.length();
    m = T.length();
    int impossible = 1;
    for(int i = n - m; i >=0; i--){
        int flag = 0;
        rep(j, m){
            if(S[i + j] != '?' && S[i + j] != T[j]){
                flag = 1;
                break;
            }
        }
        if(flag == 0){
            rep(j, n){
                if(ans[j] == '?') ans[j] = 'a';
            }
            rep(j, m){
                ans[i + j] = T[j];
            }
            impossible = 0;
            break;
        }
    }
    if(impossible) cout << "UNRESTORABLE" << "\n";
    else cout << ans << "\n";
    return 0;
}

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

using namespace std;
using ll = long long;
using P = pair<int, int>;
#define all(c) (c).begin(), (c).end()
const int INF = 1e9 + 1;
const ll LINF = 1e18 + 1;
const ll MOD = 1e9 + 7;

template <class T>
T fast_pow(T n, int exp) {
  T ret = 1, powOf2 = n;
  while (exp > 0) {
    if (exp & 1) ret *= powOf2;
    powOf2 *= powOf2;
    exp /= 2;
  }
  return ret;
}

class modint {
 public:
  ll n;
  int mod = MOD;

  modint(const ll x = 0) noexcept : n(x) {}
  modint inverse() { return fast_pow(*this, mod - 2); }
  modint& operator+=(const modint a) {
    n += a.n;
    n %= mod;
    return *this;
  }
  modint operator+(const modint a) { return modint(*this) += a; }
  modint& operator-=(const modint a) {
    n += (mod - a.n);
    n %= mod;
    return *this;
  }
  modint operator-(const modint a) { return modint(*this) -= a; }
  modint& operator*=(const modint a) {
    n *= a.n;
    n %= mod;
    return *this;
  }
  modint operator*(const modint a) { return modint(*this) *= a; }
  modint& operator/=(modint a) { return (*this) *= a.inverse(); }
  modint operator/(const modint a) { return modint(*this) /= a; }
};
ostream& operator<<(ostream& o, const modint& m) {
  o << m.n;
  return o;
}

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

  int n, a1;
  cin >> n >> a1;

  vector<int> cnt = {1, 0, 0};
  modint ans = 3;
  for (int i = 1; i < n; ++i) {
    int m, p = 0, t = 0;
    cin >> m;
    for (int j = 0; j < 3; ++j) {
      if (cnt[j] == m) {
        ++p;
        t = j;
      }
    }
    ans *= p;
    ++cnt[t];
  }
  if (a1 != 0) {
    cout << 0 << endl;
    return 0;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=200000;

long long a[N+3],sum;

long long ABS(long long cur){return cur<0? -cur:cur;}
int main(){
	int n;scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]),sum+=a[i];
	long long tot=0,ans=(1ll<<60);
	for(int i=0;i<=n;i++){
		tot+=a[i];
		ans=min(ans,ABS(tot-(sum-tot)));
	}
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 1664
#pragma target("avx")
#pragma optimize("O3")
#include<bits/stdc++.h>
using ll = int_fast64_t;
using P = std::pair<ll,ll>;
using PP = std::pair<ll,P>;
using V = std::vector<ll>;
template<typename T> using pq = std::priority_queue<T>;
template<typename T> using rpq = std::priority_queue<T, std::vector<T>, std::greater<T>>;

#define REP(i,b,e) for(ll i=b; i<e; i++)
#define ALL(vec) vec.begin(),vec.end()
#define PRINT(vec) printf("[ ");for(auto &i:vec)printf("%ld ",i);puts("]");
#define SCAN(vec) for(auto &i:vec)scanf("%ld",&i)
#define fi first
#define se second

const int MOD = 1e9+7;
const ll INF = 1e18;
int dx[] = {0, 1, 0, -1, 1, 1, -1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

int main(){
	int n, a, ans = 32;
	scanf("%d", &n);
	while(n--){
		scanf("%d", &a);
		int tmp = 0;
		while(a%2==0) tmp++, a>>=1;
		ans = std::min(ans, tmp);
	}
	printf("%d\n", ans);
	return 0;
}



Measured memory_bytes: 256
def main():
    n = int(input())
    ans = []
    i = 1
    while 1:
        if i <= n:
            if i % 3 == 0:
                ans.append(i)
            else:
                hoge = list(str(i))
                if "3" in hoge:
                    ans.append(i)
            i += 1
        else:
            break
    
    print(" ", end = "")
    for x in range(len(ans)):
        if x != len(ans) - 1:
            print(ans[x], end = " ")
        else:
            print(ans[x])

if __name__ == "__main__":
    main()

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

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> x(m);
  rep(i, m) cin >> x[i];

  sort(x.begin(), x.end());

  priority_queue<int> q;
  rep(i, m - 1) q.push(x[i + 1] - x[i]);

  int ans = x[m - 1] - x[0];
  rep(i, n - 1) {
    if (q.empty()) break;
    ans -= q.top();
    q.pop();
  }

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

Measured memory_bytes: 1276
#include<bits/stdc++.h>
	using namespace std;
	#define int long long int
	#define pb push_back
	const int mod=1e9+7;
	#define all(x) x.begin(),x.end()
	#define endl '\n'
	#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
	
	int add(int x,int y){
		x+=y;
		while(x>=mod)x-=mod;
		while(x<0)x+=mod;
		return x;
	}
	int mul(int a,int b){
		return (a*b)%mod;
	}
	int fast(int a,int b){
		int res=1ll;
		while(b){
			if(b&1)res=mul(res,a);
			a=mul(a,a);
			b>>=1;
		}
		return res;
	}
	int inverse(int x){
		return fast(x,mod-2);
	}
	int divide(int a,int b){
		return mul(a,inverse(b));
		
	}
	int fact[200066];
	void factorial(){
		fact[0]=1;
		for(int i=1;i<200066;i++){
			fact[i]=mul(fact[i-1],i);
		}
	}
	
	int Comb(int n,int k){
		return divide(fact[n],mul(fact[k],fact[n-k]));
	}
	
/*-----------------------------------------------------------------------------------------------------*/	
/*-----------------------------------------------------------------------------------------------------*/	

	
	int32_t main(){
		IOS;
		int n;
		cin>>n;
		int arr[n+1];
		int cnt=0;
		for(int i=1;i<=n;i++){
			cin>>arr[i];
			if(arr[i]%2 and i%2)cnt++;
		}
		cout<<cnt<<endl;
		return 0;
	}


Measured memory_bytes: 3648
#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <ctime>
#include <complex>

using namespace std;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,b,a) for (int i = (b)-1; i >= (a); i--)
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL) INF;

const int MAX = 100 * 1000 + 47;

int main()
{
    // freopen("in.txt", "r", stdin);
    int n, m, nn, mm;
    cin >> n >> m >> nn >> mm;
    
    if (n % nn == 0 && m % mm == 0)
    {
        cout << "No" << endl;
        return 0;
    }
    
    cout << "Yes" << endl;
    int pos = 1111;
    int neg =  - (nn * mm - 1) * pos - 1;

    
    FOR(i, 0, n)
    {
        FOR(j, 0, m)
        {
            if (i % nn == nn -1 && j % mm == mm -1)cout << neg << " ";
            else cout << pos << " ";
        }
        cout << endl;
    }
    
    
    
    

    
    return 0;
}





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

using namespace std;

int main(){
    int a,b;
    //a = 5;
    //b = 5;
    cin >> a >> b;
    if(a <= b){
        cout << min(a,b) << endl;
    }else{
        cout << a - 1 << endl;
    }


}

Measured memory_bytes: 256
#B
n,x = [int(i) for i in input().split()]
ans = x
a = x
p = n-x
while(1):
    q,r = divmod(a,p)
    ans += p * 2* q
    if r==0:
        print(ans)
        break
    else:
        ans += p
        ans += r
        a = p -r 
        p = r        

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <time.h>
#define int long long int
#define pb push_back
#define all(a) a.begin(), a.end()
#define scnarr(a, n) for (int i = 0; i < n; ++i) cin >> a[i]
#define vi vector<int>
#define si set<int>
#define pii pair <int, int>
#define sii set<pii>
#define vii vector<pii>
#define mii map <int, int>
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;
using namespace chrono;
/*
	Things to remember : check for coners n = 1, pass references instead
*/
/* -------------------------------Solution Sarted--------------------------------------*/

//Constants
const int MOD = 1000000007; // 1e9 + 7
const int MAXN = 1000005; // 1e6 +5
const int INF = 100000000000005; // 1e15 +5

void solve(){
	int k;
	cin >> k;
	int num = 7, cnt = 1;
	while(num%k and cnt <= 10000000){
		num = (num%k) *10 +7;
		cnt++;
	}


	cout << (cnt >= 10000000 ? -1 : cnt) << endl;
}

signed main()
{
	faster;
#ifndef ONLINE_JUDGE
	freopen("ip.txt", "r", stdin);
	freopen("op.txt", "w", stdout);
#endif
	// int t; cin >> t; while(t--)
		solve();
	return 0;
}


//Author : Ankit Raj
//Problem Link :

/*Snippets*/
/*
sieve - prime factorization using sieve and primes in range
zpower - pow with mod
plate - Initial template
bfs 
dfs
fenwik - BIT
binary_search
segment_tree
*/
	

Measured memory_bytes: 3632
A, B = map(int, input().split())
 
N_A = A / 0.08
N_B = B / 0.1
A_list = [int(N_A + i) for i in range(20) if A <= int(N_A+i)*0.08 < A+1]
B_list = [int(N_B + i) for i in range(20) if B <= int(N_B+i)*0.1 < B+1]
 
N_min = float('inf')
for i in B_list:
    if i in set(A_list) and i < N_min:
        N_min = i
if N_min == float('inf'):
    print(-1)
else:
    print(N_min)

Measured memory_bytes: 3064
N, K, Q = map(int, input().split())

A = []
for i in range(Q):
    A.append(int(input()))

se = [K-Q for i in range(N)]

for i in range(Q):
    se[A[i]-1] += 1


for i in range(N):
    if se[i] > 0:
        print('Yes')
    else:
        print('No')

Measured memory_bytes: 11764
#include <cstdio>
#define MAX 10005
#define NIL -1

typedef struct pp{int p,l,r;} Node;
Node T[MAX];
int n;

/*先行巡回*/

void preParse(int u){
  if(u==NIL) return;
  printf(" %d",u);
  preParse(T[u].l);
  preParse(T[u].r);
}

void inParse(int u){
  if(u==NIL) return;
  inParse(T[u].l);
  printf(" %d",u);
  inParse(T[u].r);
}

void postParse(int u){
  if(u==NIL) return;
  postParse(T[u].l);
  postParse(T[u].r);
  printf(" %d",u);
}

int main(){
  int i,v,l,r,root;
  scanf("%d", &n);
  for(i=0;i<n;i++) T[i].p=NIL;
  for(i=0;i<n;i++){
    scanf("%d %d %d", &v, &l, &r);
    T[v].l=l;
    T[v].r=r;
    if(l!=NIL) T[l].p=v;
    if(r!=NIL) T[r].p=v;
  }
  
  for(i=0;i<n;i++) if(T[i].p==NIL) root =i;
  printf("Preorder\n");
  preParse(root);
  printf("\n");
  printf("Inorder\n");
  inParse(root);
  printf("\n");
  printf("Postorder\n");
  postParse(root);
  printf("\n");
  
  return 0;
}


Measured memory_bytes: 2696
#include <iostream>
#include <vector>
#include <queue>


int main() {
	int n, q;
	std::cin >> n >> q;
	int a[n - 1], b[n - 1];
	std::vector<std::vector<int> > hen(n);
	for (int i = 0; i + 1 < n; i++) {
		std::cin >> a[i] >> b[i];
		a[i]--;
		b[i]--;
		hen[a[i]].push_back(b[i]);
		hen[b[i]].push_back(a[i]);
	}
	std::vector<int> num(n);	
	for (int i = 0; i < q; i++) {
		int p, x;
		std::cin >> p >> x;
		p--;
		num[p] += x;
	}
	
	
	std::queue<int> que;
	que.push(0);
	std::vector<bool> used(n);
	used[0] = true;
	while (que.size()) {
		int i = que.front();
		que.pop();
		for (auto j : hen[i]) {
			// i -> j
			if (used[j]) continue;
			used[j] = true;
			num[j] += num[i];
			que.push(j);
		}
	}
	for (int i = 0; i < n; i++) std::cout << num[i] << " ";
	

	return 0;
}


Measured memory_bytes: 17140
#include <iostream>
#include <string>
#include <cstdlib>

using namespace std;

int ok(string S, string T, int k){
	for (int i = 0; i < T.size(); i++){
		if (S[k+i] == T[i] || S[k+i] == '?')
			;
		else
			return 0;
	}

	return 1;
}

int main(void){
	string Sp, T;

	cin >> Sp >> T;

	if (Sp.size() < T.size()){
		cout << "UNRESTORABLE" << endl;
	}
	else {
		int a = Sp.size() - T.size();
		for (int i = a; i >= 0; i--){
			if (ok(Sp, T, i)){
				int idx = 0;
				for (int j = 0; j < Sp.size(); j++){
					if (j >= i && j < i+T.size()){
						cout << T[idx];
						idx++;
					}
					else {
						if (Sp[j] == '?')
							cout << 'a';
						else
							cout << Sp[j];
					}
				}
				cout << endl;
				break;
			}
			if (i == 0)
				cout << "UNRESTORABLE" << endl;
		}
	}


	return 0;
}

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

int main() {
  int N;
  cin >> N;
  int A, B, C, D, E, F, G, H, I, a, b, c, d, e, f, g, Z, Q;
  A = N/100000000;
  a = N%100000000;
  B = a/10000000;
  b = a%10000000;
  C = b/1000000;
  c = b%1000000;
  D = c/100000;
  d = c%100000;
  E = d/10000;
  e = d%10000;
  F = e/1000;
  f = e%1000;
  G = f/100;
  g = f%100;
  H = g/10;
  I = g%10;
  
  Z = A + B + C + D + E + F + G + H + I;
  Q = N%Z;
  if (Q == 0){
    cout << "Yes" << endl;
  }
  else if (Q != 0){
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define pb push_back
#define M 1000000007
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
const int N = 2e5 + 1 , md = 998'244'353;
int n , q , seg[4*N] , lazy[4*N] , pw[N] , ones[N];
int mult(ll a , ll b){
	return (a*b)%md;
}
int ad(ll a , ll b){
	ll ret = a + b;
	if(ret >= md) ret -= md;
	return ret;
}
void build(int c , int l , int r){
	if(l == r){
		seg[c] = 1;
		return;
	}
	build(2*c+1 , l , (l+r)/2);
	build(2*c+2 , (l+r)/2+1 , r);
	seg[c] = ad(mult(seg[2*c+1] , pw[r - (l+r)/2]) , seg[2*c+2]);
}
void fix(int c , int l , int r){
	if(lazy[c] == -1)return;
	seg[c] = mult(lazy[c] , ones[r-l+1]);
	if(l != r)lazy[2*c+1] = lazy[2*c+2] = lazy[c];
	lazy[c] = -1;
}
void update(int c , int l , int r , int s , int e , int d){
	fix(c , l , r);
	if(e < l || s > r) return;
	if(s <= l && e >= r){
		lazy[c] = d;
		fix(c , l , r);
		return;
	}
	update(2*c+1 , l , (l+r)/2 , s , e , d);
	update(2*c+2 , (l+r)/2+1 , r , s ,e , d);
	seg[c] = ad(mult(seg[2*c+1] , pw[r-(l+r)/2]) , seg[2*c+2]);
}
int main(){	
	pw[0] = 1;
	for (int i = 1 , tmp = 0; i < N; ++i){
		pw[i] = mult(pw[i-1] , 10);
		tmp = ad(mult(tmp , 10) , 1);
		ones[i] = tmp;
	}
	scanf("%d%d",&n,&q);
	build(0 , 0 , n-1);
	memset(lazy , -1 , sizeof lazy);
	while(q--){
		int l , r , d;
		scanf("%d%d%d",&l,&r,&d);
		update(0 , 0 , n-1 , l-1 , r-1 , d);
		printf("%d\n",seg[0]);
	}

}	

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

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> price(N);
  for (int i = 0; i < N; i++) {
    cin >> price.at(i);
  }
  sort(price.begin(), price.end());
  int sum = 0;
  for (int i = 0; i < M; i++) {
    sum += price.at(i);
  }
  cout << sum << endl;
}

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

int main(){
    string str; cin >> str;
    int q; cin >> q;

    string order;
    int a,b;
    string restr;

    for (int i = 0; i < q; i++)
    {
        cin >> order >> a >> b;

        if (order == "replace")
        {
            cin >> restr;
            str.replace(a, b-a+1, restr);
        }

        if (order == "reverse")
        {
            int left = a;
            int right =b;
            while(left<right){
                swap(str[left++], str[right--]);
            }
        }

        if (order == "print")
        {
            for (int i = a; i <= b; i++)
            {
                cout << str[i];
            }
            cout << endl;
            
        }
        
        
        
    }
    
}


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

using namespace std;

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

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

    for(int i=0;i<3;i++){
        if(!a[3*i] && !a[1+3*i] && !a[2+3*i]){
            cout << "Yes" << endl;
            return 0;
        }
        if(!a[i] && !a[i+3] && !a[i+6]){
            cout << "Yes" << endl;
            return 0;
        }
    }
    if(!a[2] && !a[4] && !a[6]){
       cout << "Yes" << endl;
       return 0;
    }
    if(!a[0] && !a[4] && !a[8]){
       cout << "Yes" << endl;
       return 0;
    }
    cout << "No" << endl;
}

Measured memory_bytes: 256
#ifndef LOCAL
#pragma GCC optimize("O3")
#endif
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
using namespace __gnu_pbds;
#define sim template < class c
#define int long long
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << '\n'; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);
typedef tree< pair<int,int>, null_type, less<pair<int,int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
const ll MOD = 1e9 + 7 ;
const ll N = 1e5 + 10 ;
const ll INF = 1e18 + 10 ;
vector<int> fact(N) ;
int fast(int a, int b){
    if ( b == 0 ) return 1 ;
    if ( b == 1 ) return a ;
    int y = fast(a, b / 2) % MOD;
    int ans = y * y ; 
    ans %= MOD ;
    if ( b & 1 ) ans *= a ;
    return ans % MOD ; 
}
int inverse(int x){
    return fast(x, MOD - 2) ;
}
int C(int n, int k){
    int ans = fact[n] * inverse(fact[k]);
    ans %= MOD ;
    ans *= inverse(fact[n - k]) ;
    return ans % MOD ;
}
int fix(int x){
    return (x % MOD + MOD) % MOD ;
}
signed main(){
    fastio
    fact[0] = fact[1] = 1 ;
    for(int i = 2; i < N; i++){
        fact[i] = i * fact[i - 1] ;
        fact[i] %= MOD ;
    }
    int n , k ;
    cin >> n >> k ;
    vector<int> v(n) ;
    for(int i = 0; i < n; i++){
        cin >> v[i] ;
    }
    sort(v.begin(), v.end()) ;
    int nix = 0 ; 
    int nax = 0 ;
    for(int i = 0; i < n; i++){
        int rem = n - i - 1 ;
        debug() << imie(rem) ;
        if ( rem >= k - 1 ){
            debug() << imie(C(rem, k - 1)); 
            nix += (C(rem, k - 1) * v[i]) % MOD;
            nix %= MOD ;
        }
        else break ;
    }
    reverse(v.begin(), v.end()) ;
    for(int i = 0; i < n; i++){
        int rem = n - i - 1 ;
        if ( rem >= k - 1){
            nax += (C(rem, k - 1) * v[i]) % MOD ;
            nix %= MOD ;
        }
        else break ;
    }
    debug() << imie(nax) imie(nix) ;
    int ans = nax - nix ; 
    ans = fix(ans) ;
    cout << ans << endl ;
    return 0; 
}

Measured memory_bytes: 4788
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define endl "\n"
#define sz(x) ((ll)(x).size())
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define prt(x) cout << (x)
#define prtl(x) cout << (x) << endl
#define rep(i,a,b) for(ll i=a; i<b; i++)
#define rrep(i,a,b) for(ll i=a; i>b; i--)
#define mp(a, b) make_pair(a, b)
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define debug(v) cout << #v<< ": " << v <<endl;
#define fst first
#define snd second
using namespace std;
using vi = vector<int>;
using vll = vector<long long int>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;
using vc = vector<char>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<long long int>>;
using vvc = vector<vector<char>>;
using ll = long long int;
using P = pair<long long int, long long int>;
using Map = map<long long int, long long int>;
ll INF = 1LL<<60;
ll M = 1e9+7;

/* warshall_floyd(dist,prev)
    入力：初期化した dist, prev
    計算量：O(|V|^3)
    副作用：dis[i][j]にiからjへの最短路のコストを格納、prev[i][j]にiからjへの最短路でのjの1つ前の点を格納
*/
void warshall_floyd(vector<vector<long long>> &dist, vector<vector<long long>> &prev) {
    int V = dist.size();
    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    prev[i][j] = prev[k][j];
                }
            }
        }
    }
}
 
/* get_path(prev, s, t)
    入力：warshall_floyd で得た prev, スタート s, ゴール t
    出力：s から t への最短路のパス
*/
vector<int> get_path(const vector<vector<long long>> &prev, int s, int t) {
    vector<int> path;
    for (int cur = t; cur != s; cur = prev[s][cur]) {
        path.push_back(cur);
    }
    path.push_back(s);
    reverse(path.begin(), path.end());
    return path;
}

int main(){
    ll n, m; cin >> n >> m;
    vvll dist(n+1, vll(n+1, INF));
    vvll used(n+1, vll(n+1, INF));
    rep(i, 0, m){
        ll a, b, c; cin >> a >> b >> c;
        used[a][b] = 0; used[b][a] = 0;
        dist[a][b] = c; dist[b][a] = c;
    }
    rep(i, 1, n+1){
        dist[i][i] = 0;
    }
    vvll prev(n+1, vll(n+1));
    rep(i, 1, n+1){
        rep(j, 1, n+1){
            prev[i][j] = i;
        }
    }
    warshall_floyd(dist, prev);
    rep(i, 1, n+1){
        rep(j, i+1, n+1){
            vi g = get_path(prev, i, j);
            rep(k, 0, sz(g)-1){
                used[g[k]][g[k+1]] = 1;
                used[g[k+1]][g[k]] = 1;
            }
        }
    }
    ll ans = 0;
    rep(i, 1, n+1){
        rep(j, 1, n+1){
            if(used[i][j] == 0){
                ans++;
            } 
        }
    }
    prtl(ans/2);
}


Measured memory_bytes: 3888
#include <stdio.h>

int main(){
	int n,i,j;
	scanf("%d", &n);
	int num[n];
	for(i=0; i<n; i++){
		scanf("%d", &num[i]);
	}
	int max=num[1]-num[0], min=num[0];
	
	for(i=1; i<n; i++){
			if(max<num[i]-min){
				max=num[i]-min;
			}
			if(min>num[i]){
				min=num[i];
			}
	}
	
		printf("%d\n", max);
		
	return 0;
}


Measured memory_bytes: 2524
#include<iostream>
#include<algorithm>
#include<string>
#include<utility>


using namespace std;

int main() {
	int n;
	string a[100],b[100];
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		b[i] = a[i];
	}
	bool flag = true;
	while (flag) {
		flag = false;
		for (int i = n-1; i > 0; i--) {
			if (a[i][1] < a[i - 1][1]) {
				swap(a[i], a[i - 1]);
				flag = true;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		if (i != 0)cout << " ";
		cout << a[i];
	}
	cout << endl << "Stable" << endl;
	for (int i = 0; i < n; i++) {
		int MIN = i;
		for (int j = i; j < n; j++) {
			if (b[j][1] < b[MIN][1]) {
				MIN = j;
			}
		}
		if (i != MIN) {
			swap(b[i], b[MIN]);
		}
	}
	string stb="Stable";
	for (int i = 0; i < n; i++) {
		if (i != 0)cout << " ";
		cout << b[i];
		if (a[i] != b[i])stb = "Not stable";
	}
	cout << endl << stb << endl;
	return 0;
}

Measured memory_bytes: 3216
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define ALL(a) a.begin(),a.end()
int main(){
  int n;
  while( cin >> n , n ){
    vector < int > p[n],L,tmp;
    for(int i = 0, q, d ; i < n ; i++ ){
      cin >> q;
      while(q--) cin >> d, p[i].push_back(--d);
      sort(ALL(p[i]));
    }
    int K, l, ans = -1, i;
    cin >> K;
    while(K--) cin >> l, L.push_back(--l);
    for( sort(ALL(L)), i = 0 ; i < n ; i++ ){
      if(includes(ALL(p[i]),ALL(L))){
        if(ans == -1) ans = i + 1;
        else break;
      }
    }
    cout << (i == n ? ans : -1) << endl;
  }
}

Measured memory_bytes: 1268
import java.util.Scanner;
public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		String S = sc.next();
		int max = 0,x = 0;
			for(int i = 0;i < N;i++){
				if(S.charAt(i) == 'I'){
					x = x + 1;
					max = Math.max(x,max);
				}else{
					x = x - 1;
				}
			}
			System.out.println(max);
	}
}


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

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, f, n) for(int i = (int)(f); i < (int)(n); i++)

typedef pair<int, int> P;

const int inf = 1 << 25;

struct edge
{
  int to, cost;
  edge(){}
  edge(int to, int cost):to(to), cost(cost){}
};

vector< vector<edge> > graph;
vector< vector<int> > mincost;

int dijkstra(int s)
{
  priority_queue<P, vector<P>, greater<P> > que;
  que.push(P(0, s));
  mincost[s][s] = 0;
  while(!que.empty()) {
    int cost, now;
    tie(cost, now) = que.top(); que.pop();
    if(mincost[s][now] < cost) continue;
    for(edge& e : graph[now]) {
      if(e.cost + cost < mincost[s][e.to]) {
	mincost[s][e.to] = e.cost + cost;
	que.push(P(mincost[s][e.to], e.to));
      }
    }
  }
  return *max_element(all(mincost[s]));
}

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int N, R;
  cin >> N >> R;
  graph.resize(N);
  rep(i, R) {
    int s, t, d;
    cin >> s >> t >> d; s--, t--;
    graph[s].emplace_back(t, d);
    graph[t].emplace_back(s, d);
  }

  mincost.resize(N, vector<int>(N, inf));
  int maxdist = 0;
  rep(i, N) maxdist = max(maxdist, dijkstra(i));
  //rep(i, N) reps(j, i+1, N) maxdist = max(maxdist, mincost[i][j]);

  vector<P> ep;
  //vector<int> S, T;
  rep(i, N) reps(j, i+1, N) {
    if(mincost[i][j] == maxdist) {
      ep.emplace_back(i, j);      
      //S.push_back(i), T.push_back(j);
    }
  }

  vector<int> ans;
  rep(i, N) {
    bool flag = true;
    for(auto& p : ep) {
      //rep(j, S.size()) {
      int s, t; tie(s, t) = p;
      if(mincost[s][i] + mincost[i][t] == maxdist) {      
      //if(mincost[S[j]][i] + mincost[i][T[j]] == maxdist) {
	flag = false;
	//break;
      }
    }
    if(flag) ans.push_back(i+1);
  }
  
  cout << ans.size() << endl;
  rep(i, ans.size()) cout << ans[i] << endl;
  
  return 0;
}

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



int main() {
    int n; cin >> n;
    ll sum = 0;
    vector<int> a(n+2,0),b(n+2,0);
    for(int i = 1; i <= n; i ++) {
        cin >> a[i];
    }

    for(int i = 1; i <= n; i ++){
        if((a[i-1] <= a[i] && a[i] <= a[i+1]) || (a[i-1] >= a[i] && a[i] >= a[i+1])){
            b[i] = 1;
        }
        sum += abs(a[i] -a[i-1]);
    }
    sum += abs(a[n]);

    for(int i = 1; i <= n; i ++){
        cout << sum - abs(a[i]-a[i-1]) - abs(a[i]-a[i+1]) + abs(a[i-1]-a[i+1])<< endl;
        
    }


    return 0;
}











Measured memory_bytes: 3948
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i < (b); i++)
#define rrep(i, a, b) for (int i = a; i >= (b); i--)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
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;
}
void hr() { cerr << "--------------" << endl; }
const int INF = 2e9;
const int MOD = 1e9 + 7;

int main() {
   int k, x;
   cin >> k >> x;
   rep(i, x - k + 1, x + k) { printf("%d%c", i, i != x + k - 1 ? ' ' : '\n'); }
   return 0;
}

Measured memory_bytes: 256
use proconio::input;

fn main() {
    input! {
        a: i64,
        b: i64,
        c: i64,
        k: i64,
    }

    let mut answer: i64 = 0;
    let mut count: i64 = k;

    if count <= 0 {
        println!("{:?}", answer);
        return;
    }

    if a < count {
        count -= a;
        answer += a;
    } else {
        answer += count;
        println!("{:?}", answer);
        return;
    }

    if count <= 0 {
        println!("{:?}", answer);
        return;
    }

    if b < count {
        count -= b;
    } else {
        println!("{:?}", answer);
        return;
    }

    if count <= 0 {
        println!("{:?}", answer);
        return;
    }

    if c < count {
        answer -= c;
    } else {
        answer -= count;
        println!("{:?}", answer);
        return;
    }

    println!("{:?}", answer);
}


Measured memory_bytes: 2112
import java.util.Scanner;

public class Main{


	static int a(int n){
		int min=n;
		for(int z=0; z<101; z++){
			for(int y=0; y<1001; y++){
				int x = n - (z*z*z) - (y*y);
				if(x < 0) continue;
				int sum = x+y+z;
				if(min >= sum) min = sum;
			}
		}
		return min;
	}




	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);


		while(true){
			int n = sc.nextInt();
			if(n == 0) break;

			System.out.println(a(n));

		}

	}

}

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

int main(){

  int N, M, C;
  int A[21][21];
  int B[21];

  int ans = 0;

  cin >> N >> M >> C;

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

  for(int j = 0 ; j < N ; j++){
    for(int i = 0 ; i < M ; i++){
      cin >> A[j][i];
    }
  }

  int tmp = 0;

  
  for(int i = 0 ; i < N ; i++){

    for(int j = 0 ; j < M ; j++){
      tmp += A[i][j]*B[j];
      // cout << tmp << endl;
    }
    tmp += C;
    // cout << "tmp : " << tmp << endl;
    if(tmp > 0) ans++;
    // cout << "ans : " << ans << endl;

    tmp = 0;

  }

  cout << ans << endl;

}

Measured memory_bytes: 256
#include <iostream>

int main(void)
{
	using namespace std;

	int r,c;

	cin >> r;
	cin >> c;

	int Mat[r][c];
	int sums_row[r] = {0}, sums_colmn[c] = {0}, sums_all = 0;

	for(int i=0; i<r; i++){
		for(int j=0; j<c; j++){
			cin >> Mat[i][j];
			sums_row[i] += Mat[i][j];
		}
	}

	for(int j=0; j<c ;j++){
		for(int i=0; i<r; i++)	sums_colmn[j] += Mat[i][j];
		sums_all += sums_colmn[j];
	}

	for(int i=0; i<r; i++){
		for(int j=0; j<c; j++)	cout << Mat[i][j] << " ";
		cout << sums_row[i] <<endl;
	}
	for(int j=0; j<c; j++)	cout << sums_colmn[j] << " ";
	cout << sums_all << endl;

	return 0;
}

Measured memory_bytes: 3128