akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int gcd(int a, int b) {
		if ( a < b ) swap(a, b);
		if ( b == 0 ) return a;
		else gcd(b , a % b);
}

int main() {
		int N;
		cin >> N;
		vector<int> A(N, 1);
		for (int i = 0; i < N; i++) cin >> A[i];

		int ans = A[0];
		for (int i = 1; i < N; i++) {
				ans = gcd(ans, A[i]);
		}
		cout << ans << endl;
		return 0;
}


Measured memory_bytes: 640
N = int(input())
a = list(map(int,input().split()))
odd = by2 = by4 = 0
for c in a:
    if c % 4 == 0:by4 += 1
    elif c % 2 == 0:by2 += 1
    else:odd += 1

if N == 2:
    if by4>=1:print('Yes')
    elif by2 == 2:print('Yes')
    else:print('No')
elif N == 3:
    if odd == 3:print('No')
    elif odd==2:
        if by4==1:print('Yes')
        else:print('No')
    elif odd==1:
        if by4>=1:print('Yes')
        else:print('No')
    else:print('Yes')
else:
    if by2 > 0:
        if by4-odd>=0:print('Yes')
        else:print('No')
    else:
        if by4-odd>=-1:print('Yes')
        else:print('No')

Measured memory_bytes: 14480
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1000000010
#define EPS 1e-9
#define F first
#define S second

#define debug(x) cout<<x<<endl;
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define lp(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
#define int long long
#define endl "\n"

typedef pair<int,int> PII;
typedef pair<int,string> PIS;
typedef pair<string,int> PSI;


signed main(){
  cin.tie(0);	
  ios::sync_with_stdio(false);
  string s;
  cin>>s;
  int num=0;
  rep(i,s.size() ){
    num+=s[i]-'0';
    num%=9;
  }
  if(num==0) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;


  return 0;
}


Measured memory_bytes: 3740
#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
#include<inttypes.h>

typedef int32_t i32;

double calc (i32 *t, i32 *v, i32 n) {
  if (n == 1) {
    double m = t[0] * 0.5;
    if (m <= v[0]) {
      return m * m;
    } else {
      return v[0] * v[0] + v[0] * (t[0] - 2 * v[0]);
    }
  }
  if (t[0] == 0 || v[0] == 0) return calc (t + 1, v + 1, n - 1);
  if (t[n - 1] == 0 || v[n - 1] == 0) return calc (t, v, n - 1);
  for (i32 i = 0; i < n; ++i) {
    if (v[i] == 0) {
      return calc (t, v, i) + calc (t + i + 1, v + i + 1, n - i - 1);
    }
  }
  double sum = 0;
  for (i32 i = 0; i < n; ++i) {
    sum += t[i];
    v[i]--;
  }
  t[0]--;
  t[n - 1]--;
  return sum - 1 + calc (t, v, n);
}

void run (void) {
  i32 n;
  scanf ("%" SCNi32, &n);
  i32 *t = (i32 *) calloc (n, sizeof (i32));
  for (i32 i = 0; i < n; ++i) {
    scanf ("%" SCNi32, t + i);
  }
  i32 *v = (i32 *) calloc (n, sizeof (i32));
  for (i32 i = 0; i < n; ++i) {
    scanf ("%" SCNi32, v + i);
  }
  double ans = calc (t, v, n);
  printf ("%.7f\n", ans);
}

int main (void) {
  run ();
  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

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

int main(){
    int n,a,b;
    cin >> n >> a >> b;
    if (a*n<=b)
    {
        cout << a*n << endl;
    }else
    {
        cout << b << endl;
    }
    
    
}


Measured memory_bytes: 256
# include <iostream>
# include <vector>
# include <limits>
# include <algorithm>
# include <map>
# include <string>
# include <functional>
using namespace std;

int main() {
	string s, f;
	int n;
	cin >> s >> n;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		cin >> f;
		f += f;
		for (int j = 0; j < f.size() - s.size(); j++) {
			if (f.substr(j, s.size()) == s) {
				ans++;
				break;
			}
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 3076
#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
typedef pair<int,int> Pint;
typedef pair<ll, ll> P;
//typedef pair<int, pair<int, int>> P;
//typedef tuple<int,int,int> T;
ll INFL = 1000000000000000010;//10^18 = 2^60
int INF = 2147483600;//10^9
ll MOD  = 1000000007;
vector<int> dy = {0,0,1,-1};
vector<int> dx = {1,-1,0,0};

int main(void){
    cin.tie(0);
   	ios::sync_with_stdio(false);
   	int N, D, X;
   	cin >> N >> D >> X;
   	int ans = X;
   	for(int i = 0; i < N; i++){
   	    int A; cin >> A;
   	    ans += (D - 1) / A + 1;
   	}
   	cout << ans << endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
// #include <boost/multiprecision/cpp_int.hpp>
#define ll long long
#define llu unsigned long long
#define ld long double
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define PI 3.14159265
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define deb(x) cerr << ">> " << #x << " : " << x << "\n"
#define endl '\n'
#define ff first
#define ss second
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a * b) / __gcd(a, b)
#define DESYNC ios::sync_with_stdio(0); cin.tie(0);
#define print(a) for(auto x : a) cout << x << " "; cout << endl;

using namespace std;


const ll inf = 1e18 + 42;

const ll M = 998244353;

ll power(ll x, ll y) {
	if (y == 0) return 1;
	if (y & 1) return (x * power(x, y - 1));
	ll t = power(x, y / 2);
	return (t * t);
}

const ll MAX = 1e5 + 5;

// +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

ll dp[MAX];

void ahShitHereWeGoAgain()
{
	ll n;
	cin >> n;
	vector<ll> a(n);
	for(ll i = 0; i < n; i++)
		cin >> a[i];
	memset(dp, 0, sizeof(dp));

	dp[1] = abs(a[1] - a[0]); 
	deb(dp[1]);

	for(ll i = 2; i < n; i++)
	{
		dp[i] = min(dp[i - 1] + abs(a[i] - a[i - 1]), dp[i - 2] + abs(a[i] - a[i - 2]));

	}

	cout << dp[n - 1] << endl;
}

int main()
{
	DESYNC	
	ll t = 1;
	// cin >> t;
	while (t--)
		ahShitHereWeGoAgain();
	return 0;
}



Measured memory_bytes: 1792
'use strict'

function main(input) {
  const inputList = input.split(' ');
  const a = parseInt(inputList[0])
  const b = parseInt(inputList[1])
  const c = parseInt(inputList[2])
  const k = parseInt(inputList[3])

  let result = 0
  if (a > k) {
    result = k
  } else if (a+b > k) {
    result = a
  } else {
    const tmpc = k - (a + b)
    result = a - tmpc
  }
  console.log(result)
}

main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 29812
#include<stdio.h>

#define M 8
#define free 0
#define notfree 1

int n;
int T[M][M];
int row[M],col[M],dpos[2*M-1],dneg[2*M-1];

void printBoard(void){
  int i,j;

  for(i=0; i<M; i++){
    for(j=0; j<M; j++){
      if(T[i][j] == notfree){
	if(row[i] != j)return;
      }
    }
  }

  for(i=0; i<M; i++){
    for(j=0; j<M; j++){
      if(row[i] == j){
	printf("Q");
      }
      else printf(".");
    }
    printf("\n");
  }
}

void putQueen(int i){
  int j;
  
  if(i == M){
    printBoard();
    return;
  }

  for(j=0; j<M; j++){
    if(col[j] == notfree || dpos[i+j] == notfree || dneg[i-j+M-1] == notfree) continue;
    row[i] = j;
    col[j] = dpos[i+j] = dneg[i-j+M-1] = notfree;
    putQueen(i+1);
    col[j] = dpos[i+j] = dneg[i-j+M-1] = free;
  }
}

int main(){
  int i,j;
  int r,c;

  scanf("%d",&n);

  for(i=0; i<M; i++){
    for(j=0; j<M; j++){
      T[i][j] = free;
    }
  }

  for(i=0; i<M; i++){
    col[i] = free;
    row[i] = free;
  }

  for(i=0; i<2*M-1; i++){
    dpos[i] = free;
    dneg[i] = free;
  }

  for(i=0; i<n; i++){
    scanf("%d %d",&r,&c);
    T[r][c] = notfree;
  }

  putQueen(0);

  return 0;
}



Measured memory_bytes: 2084
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
struct Edge{
	int from,to,weight;
	Edge(int from,int to,int weight):
		from(from),to(to),weight(weight){}
	
};
struct Node{
	int cost;
	int num;
	bool visited;
};
Node node[100];
inline bool operator<(const Edge &e,const Edge &f){
	return e.weight!=f.weight?e.weight>f.weight:
		e.from!=f.from?e.from<f.from:e.to<f.to;
}
inline bool operator<(const Node &e,const Node &f){
	return e.cost!=f.cost?e.cost>f.cost:false;
}
using namespace std;

int main(){
	int a,b;
	while(scanf("%d%d",&a,&b),a){
		vector<vector<Edge> > graph(a);
		for(int i=0;i<b;i++){
			int type;
			scanf("%d",&type);
			if(!type){
				for(int j=0;j<a;j++){
					node[j].cost=-1;
					node[j].visited=false;
					node[j].num=j;
				}
				int c,d;
				scanf("%d%d",&c,&d);
				node[c-1].cost=0;
				priority_queue<Node > Q; // cost,where
				Q.push(node[c-1]);
				while(Q.size()){
					Node now=Q.top();
					Q.pop();
					node[now.num].visited=true;
					for(int j=0;j<graph[now.num].size();j++){
						int to=graph[now.num][j].to;
						int cost=now.cost+graph[now.num][j].weight;
						if(node[to].cost<0||node[to].cost>cost){
							node[to].cost=cost;
							Q.push(node[to]);
						}
					}
				}
				printf("%d\n",node[d-1].cost);
			}else{
				int c,d,e;
				scanf("%d%d%d",&c,&d,&e);
				graph[c-1].push_back(Edge(c-1,d-1,e));
				graph[d-1].push_back(Edge(d-1,c-1,e));
			}
		}
	}
}

Measured memory_bytes: 868
#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <map>
#include <unordered_map>
#define rep(i, n) for (int i = 0; i < n; i++)
#define ALL(a) (a).begin(), (a).end()
typedef long long ll;
using namespace std;
const int N = 2e5 + 5;
 
using namespace std;

int main() 
{
    int m;
    int n;
    int a[10], b;
 
    cin >> m;
    cin >> n;
 
    for (int i = 0; i < 10; i++){
        a[i] = 0;
    }
 
    for (int i = 0; i < n; i++){
        cin >> b;
        a[b]++;
    }
 
    for (int i = m; i < 100000; i++){
        b = i;
        while (b != 0){
            if (a[b % 10] != 0){
                break;
            }
            b /= 10;
        }
        if (b == 0){
            cout << i << endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 3584
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    a, b, c, x, y = map(int, input().split())
    p1 = a * x + b * y
    p2 = max(x, y) * 2 * c
    p3 = min(x, y) * 2 * c + ((x - y) * a if x > y else (y - x) * b)
    r = min(p1, p2, p3)
    print(r)

if __name__ == '__main__':
    main()


Measured memory_bytes: 9108
N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
cnt = 0
for i in range(N):
    beat = min(A[i], B[i])
    cnt += beat
    A[i] -= beat
    B[i] -= beat
    beat = min(A[i+1], B[i])
    cnt += beat
    A[i+1] -= beat
    B[i] -= beat
print(cnt)

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

int main() {
  string S;
  cin >> S;
  reverse(S.begin(), S.end());

  vector<string> lst = { "dream", "dreamer", "erase", "eraser" };
  for (int i = 0; i < 4; i++) reverse(lst.at(i).begin(), lst.at(i).end());

  bool ans_flag = true;

  for (int i = 0; i < S.size(); i++) {
    bool canDivide = false;
    for (int j = 0; j < 4; j++) {
      string t = lst.at(j);
      if (S.substr(i, t.size()) == t) {
        canDivide = true;
        i += t.size() - 1;
        break;
      }
    }
    if (!canDivide) {
      ans_flag = false;
      break;
    }
  }

  if (ans_flag) cout << "YES" << endl;
  else cout << "NO" << endl;
}

Measured memory_bytes: 512
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <map>

using namespace std;

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

int maxm;
int maxw;
int vs[SUPmaxm];
int wos[SUPmaxm];
int dp[SUPmaxm][SUPmaxw]; //m ika no item tukatte, w ika no omomi de, sum v no max
int rev,rew;

void solve(){
	rev=0;rew=maxw;
	FOR(m,0,maxm+1) FOR(w,0,maxw+1) dp[m][w]=0;
	FOR(m,1,maxm+1){
		FOR(w,0,maxw+1){
			if(w<wos[m]) dp[m][w] = dp[m-1][w];
			else dp[m][w] = max(dp[m-1][w],dp[m-1][w-wos[m]]+vs[m]);
			if(dp[m][w]>rev||(dp[m][w]==rev&&w<rew)){rev=dp[m][w];rew=w;}
		}
	}
}

int main(){
	for(int casei=1;true;++casei){
		scanf("%d",&maxw);			if(!maxw) return 0;
		scanf("%d",&maxm);
		FOR(m,1,maxm+1) scanf("%d,%d",vs+m,wos+m);
		solve();
		printf("Case %d:\n%d\n%d\n",casei,rev,rew);
	}
}

Measured memory_bytes: 5108
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int a = 0;
        Scanner sc = new Scanner(System.in);
        while(true) {
             int x = sc.nextInt();
             String op = sc.next();
             int y = sc.nextInt();
            if(op.equals("+")){
                a = x+y;
            }
            if(op.equals("-")){
                a = x-y;       
            }
            if(op.equals("*")){
                a = x*y;
            }
            if(op.equals("/")){
                a = x/y;
            }
            if(op.equals("?")){
                sc.close();
                break;      
            }
            System.out.println(a);
        }
    }
}


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

#define FOR(i, a, b) for (int (i) = (a); (i) < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cerr << #x << " " << x << endl
#define eb emplace_back
#define __ << " " <<
typedef long long ll;
typedef std::pair<int, int> P;
#define X first
#define Y second
#define double long double
using namespace std;

const int MaxN = 200100;
const int Mod = 1e9 + 7;

int N;
int a[2][MaxN];

void load(){
  cin>>N;
  REP(i, N) cin>>a[0][i];
  REP(i, N) cin>>a[1][i];

  int sve = -1;

  REP(k, N){
    int res = 0;
    REP(i, k + 1){
      res += a[0][i];
    }
    FOR(i, k, N){
      res += a[1][i];
    }

    sve = max(sve, res);
  }

  cout << sve << endl;
}

int main(){
    load();	
    return 0;
}



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

#define rep( i, n, m ) for(int i = ( n ); i < ( m ); i++)
#define rep_d( i, n, m ) for(int i = ( n ) - 1; i >= ( m ); i--)
#define sort_asc( X ) sort(( X ).begin(), ( X ).end())
#define sort_desc( X ) sort(( X ).begin(), ( X ).end(), greater <>())
#define endl "\n"

template <class T> bool chmax( T& a, T b );
template <class T> bool chmin( T& a, T b );
int* eratosthenes( int N );
bool bit_search( int pattern, int N );
void initialize( void );

const ll INF = 1LL << 60;
const int k_mod = 1e9 + 7;
template <typename T, typename K> struct P {
	T a; K b;
};
typedef struct {
	vector <int> to;
	int cost;
} edge;

int main( void ){
	// initialize();
	string status[] = {"AC", "WA", "TLE", "RE" };
	map <string, int> mp;
	rep( i, 0, 4 )
	mp[ status[ i ] ] = 0;
	int N;
	cin >> N;
	rep( i, 0, N ){
		string s; cin >> s;
		mp[ s ]++;
	}

	rep( i, 0, 4 )
	cout << status[ i ] << " x " << mp[ status[ i ] ] << endl;

}




template <class T> bool chmax( T& a, T b ) {
	if (a < b){
		a = b; return true;
	}
	return false;
}
template <class T> bool chmin( T& a, T b ) {
	if (a > b){
		a = b; return true;
	}
	return false;
}
int* eratosthenes( int N ){
	int* prime_array = new int[ N + 1 ];
	int lim = N;
	prime_array[ 0 ] = 0;
	prime_array[ 1 ] = 0;
	rep( i, 2, N + 1 ){
		prime_array[ i ] = 1;
	}
	rep( i, 2, lim ){
		if (prime_array[ i ] == 0)
			continue;
		lim = N / i;
		for(int j = i * 2; j < N + 1; j += i){
			prime_array[ j ] = 0;
		}
	}
	return prime_array;
}
bool bit_search( int pattern, int N ){
	int cnt = 0;
	rep( bit, 0, N ){
		if (pattern & ( 1 << bit )){
			cnt++;
		}
	}
	return true;
}
void initialize( void ){
	cout << fixed << setprecision( 10 );
}


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

using namespace std;
typedef long long ll;

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

  if (p == 2 || p == 5)
  {
    ll ans = 0;
    for (ll i = s.size() - 1; i >= 0; i--)
    {
      ll digit = s.at(i) - '0';
      if (digit % p == 0)
      {
        ans += i + 1;
      }
    }
    cout << ans << endl;
    return 0;
  }

  reverse(s.begin(), s.end());
  vector<ll> acc = {};
  map<ll, ll> cnts = {};
  cnts[0] = 1; // 範囲外を選択する場合を考慮

  ll d = 1;
  for (ll i = 0; i < s.size(); i++)
  {
    ll digit = s.at(i) - '0';
    ll val = d * digit;
    if (i > 0)
    {
      val += acc[i - 1];
    }

    val %= p;
    acc.push_back(val);

    if (cnts.count(val) > 0)
      cnts[val]++;
    else
      cnts[val] = 1;

    d *= 10;
    d %= p;
  }

  ll ans = 0;
  for (auto x : cnts)
  {
    if (x.second > 0)
    {
      ans += x.second * (x.second - 1) / 2;
    }
  }

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


Measured memory_bytes: 3772
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define mod (ll)(1e9+7)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
int N,M;
const int nmax = 50;
int graph[nmax+1][nmax+1]={0};

bool isBridge(int a, int b){
    vector<vector<int>> g(N+1,vector<int>(N+1,0));
    REP(i,N+1){
        REP(j,N+1) g[i][j]=graph[i][j];
    } 
    g[a][b] = 0;
    g[b][a] = 0;
    bool ret = false;
    bool update = true;
    while(update){
        update = false;
        for(int i=1;i<=N;i++){
            for(int j=i+1;j<=N;j++){
                if(g[i][j]==0){
                    for(int k=1;k<=N;k++){
                        if(g[i][k]==1&&g[k][j]==1){
                            g[i][j]=1;
                            g[j][i]=1;
                            update = true;
                            break;
                        }
                    }
                }
            }   
        }
    }
    if(g[a][b]==0){
        ret = true;
    }
    return ret;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> M;
    vector<int> a(M);
    vector<int> b(M);
    REP(i,M){
        cin >> a[i] >> b[i];
        graph[a[i]][b[i]] = 1;
        graph[b[i]][a[i]] = 1;
    }
    int ans = 0;
    REP(i,M){
        if(isBridge(a[i],b[i])){
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

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

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

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

int main(){
    int a;
    int b;
    int sum;
    cin >> a >> b;
    int tmp=b-a-1;
    sum=tmp*(tmp+1)/2;
    cout << sum-a << endl;

    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
//#include<boost/multiprecision/cpp_int.hpp>
//#include<boost/multiprecision/cpp_dec_float.hpp>
//namespace mp=boost::multiprecision;
//#define mulint mp::cpp_int
//#define mulfloat mp::cpp_dec_float_100
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
constexpr int MOD=1000000007;
//constexpr int MOD=998244353;
#define INF (1<<30)
#define LINF (lint)(1LL<<56)
#define endl "\n"
#define rep(i,n) for(lint (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(lint (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcountll(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
#define plint pair<lint,lint>
#define fi first
#define se second
typedef long long lint;
int dx[8]={1,1,0,-1,-1,-1,0,1};
int dy[8]={0,1,1,1,0,-1,-1,-1};
const int MAX_N=2e5+5;
//struct edge{lint to,num;};
//vector<int> bucket[MAX_N/1000];

typedef vector<vector<lint>> mat;

mat mtx{
    {1,1,0},//F(N-1),F(N-2),...,F(N-K)の係数
    {1,0,0},//1は単位元(ex.積なら1,ANDなら2^N-1)
    {0,1,0},//0は零元(ex.積やANDなら0,ORなら2^N-1?)
}; // K次正方行列

vector<lint> F{1,1,2}; //F(1)~F(K)の値

mat mul(mat &A,mat &B){
    mat C(A.size(),vector<lint>(B[0].size()));
    rep(i,A.size()) rep(j,B.size()) rep(k,B[0].size()){
        C[i][k]=(C[i][k]+A[i][j]*B[j][k])%MOD; //演算 適宜演算子を変える
    }
    return C;
}

mat powmat(mat A,lint n){
    mat B(A.size(),vector<lint>(A.size()));
    rep(i,A.size()) B[i][i]=1; //単位元 零元が0じゃない時はそこも自分で埋める
    while(n){
        if(n&1) B=mul(B,A);
        A=mul(A,A);
        n>>=1;
    }
    return B;
}

lint calc(lint n){ //F(N)の計算
    if(n==0) return 0;
    mat A=mtx;
    A=powmat(A,n-1);
    lint res=0; //零元
    rep(i,A.size()) res=(res+A[A.size()-1][i]*F[A.size()-1-i])%MOD;//演算 適宜演算子を変える
    return res;
}


/*
定数項がある場合、定数をXとして
    {1,0,1,X},//F(N-1),F(N-2),...,F(N-K)の係数,X
    {1,0,0,0},
    {0,1,0,0},
    {0,0,0,1}.

    F{1,f1,f2,f3};
答えの計算パートが
rep(i,A.size()) res=(res+A[A.size()-2][i]*F[A.size()-1-i])%MOD;
となる
*/

int main(void){
    lint N,K;
    cin >> N >> K;
    mat A(N,vector<lint>(N));
    rep(i,N) rep(j,N) cin >> A[i][j];
    A=powmat(A,K);
    lint ans=0;
    rep(i,N) rep(j,N) ans=(ans+A[i][j])%MOD;
    cout << ans << endl;
}

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

using namespace std;

#define int long long

void solve() {
    int n;
    cin >> n;
    pair <int, int> a[n];
    for (int i = 0; i < n; ++i) cin >> a[i].first;
    for (int i = 0; i < n; ++i) a[i].second = i;
    sort(a, a + n);
    reverse(a, a + n);
    vector <vector <int> > dp(n, vector <int> (n + 1));
    dp[0][0] = a[0].first * abs(n - 1 - a[0].second);
    dp[0][1] = a[0].first * abs(a[0].second);
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j <= i; ++j) {
            int l = j, r = n - 1 - (i - j);
            if (dp[i - 1][j] && j + 1 <= n) dp[i][j + 1] = max(dp[i][j + 1], dp[i - 1][j] + a[i].first * abs(l - a[i].second));
            if (dp[i - 1][j]) dp[i][j] = max(dp[i][j], dp[i - 1][j] + a[i].first * abs(r - a[i].second));
        }
    }
    int ans = 0;
    for (int i = 0; i <= n; ++i) ans = max(ans, dp[n - 1][i]);
    cout << ans;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}



Measured memory_bytes: 34612
//BISMILLAHHIR RAHMANIR RAHIM
#include<bits/stdc++.h>
using namespace std;
typedef long long int            ll;
typedef unsigned long long int   ull;
#define min3(a,b,c)              min(a,min(b,c))
#define F                        first
#define S                        second
#define PB                       push_back
#define MP                       make_pair
#define PI                       2*acos(0.0)
#define REP(i,a,b)               for(int i = a; i<=b; i++)
int main()
{
    int n,r,dis,rat;
    cin>>n>>r;
    if(n<10){
        rat=100*(10-n);
        dis=r+rat;
        cout<<dis<<endl;
    }
    else{
        cout<<r<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
int main()
{
    int n, m;
    int h[100010];
    int g[100010] = {}; //0 is good
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &h[i]);
    }
    int a, b;
    for (int i = 0; i < m; i++)
    {
        scanf("%d %d", &a, &b);
        a--;
        b--;
        if (h[a] >= h[b])
        {
            g[b] = 1;
        }
        if (h[a] <= h[b])
        {
            g[a] = 1;
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        if (g[i] == 0)
        {
            ans++;
        }
    }
    printf("%d", ans);
    return 0;
}

Measured memory_bytes: 2512
#include <vector>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(int argc, char* argv[])
{
	//ABC164 A
	int s, w;
	// S W 整数 1 -- 100

	cin >> s >> w;

	if (s <= w) {
		cout << "unsafe";
	}
	else {
		cout << "safe";
	}

	return 0;
}

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

int main(){
  ll x,y,z,a,b;
  cin >>x>>y>>z>>a>>b;
  if(2*z<=x+y){
    if(a>b && 2*z<x){
      cout << 2*z*a <<endl;
    }
    else if(b>a && 2*z<y){
      cout << 2*z*b <<endl;
    }
    else{
      if(a>=b){
        cout << 2*b*z+(a-b)*x <<endl;
      }
      else{
        cout << 2*a*z+(b-a)*y <<endl;
      }
    }
  }
  else{
    cout << a*x+b*y <<endl;
  }
}



Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}
#define vi vector<int>
#define pb(a) push_back(a)
using namespace std;

typedef long long ll;

typedef pair<int,int> P1;
typedef pair<int,P1> P2;
typedef pair<ll,int> Pli;
const int inf=1000000000;
struct edge{
	int myc,to,c,cost;
};
struct pos{
	int to,cost,color;
};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

#define MAX_N 100005

int dp[MAX_N];
vector<Pli> G1,G2;
bool d[MAX_N]={};
queue<int> que;
ll a[MAX_N]={};
ll b[MAX_N]={};
ll c[MAX_N]={};


int main() {
	int n,k;
	cin>>n>>k;
	rep(i,n)cin>>a[i+1];

	rep(i,n){
		b[i+1]=b[i];
		if(a[i+1]>0)b[i+1]+=a[i+1];
		c[i+1]=c[i]+a[i+1];
	}
	ll t=0;

	rep(i,n-k+1){
		ll c2=max((ll)0,c[i+k]-c[i]);
		t=max(t,b[i]+c2+b[n]-b[i+k]);
//		cout<<t<<endl;
	}
	cout<<t<<endl;
	return 0;
}


Measured memory_bytes: 2560
n=int(input())
a,b=[0]*n,[0]*n
for i in range(n):
  a[i],b[i]=map(int,input().split())
a.sort()
b.sort()
if n%2==1:
  print(b[n//2]-a[n//2]+1)
else:
  print((b[n//2]+b[n//2-1])-(a[n//2]+a[n//2-1])+1)

Measured memory_bytes: 25352
#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <unordered_map>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <bitset>
#include <assert.h>
#include <unordered_map>
#include <fstream>
#include <ctime>
#include <complex>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef pair<ll,ll> P;
typedef pair<int,int> pii;
typedef vector<P> vpl;
typedef tuple<ll,ll,ll> tapu;
#define rep(i,n) for(int i=0; i<(n); i++)
#define REP(i,a,b) for(int i=(a); i<(b); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int inf = 1<<30;
const ll linf = 1LL<<62;
const int MAX = 510000;
ll dy[8] = {1,-1,0,0,1,-1,1,-1};
ll dx[8] = {0,0,1,-1,1,-1,-1,1};
const double pi = acos(-1);
const double eps = 1e-7;
template<typename T1,typename T2> inline bool chmin(T1 &a,T2 b){
	if(a>b){
		a = b; return true;
	}
	else return false;
}
template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){
	if(a<b){
		a = b; return true;
	}
	else return false;
}
template<typename T> inline void print(T &a){
    for(auto itr = a.begin(); itr != a.end(); itr++){
		cout << *itr << " ";
	}
    cout << "\n";
}
template<typename T1,typename T2> inline void print2(T1 a, T2 b){
	cout << "debug: " << a << " " << b << "\n";
}
template<typename T1,typename T2,typename T3> inline void print3(T1 a, T2 b, T3 c){
	cout << "debug: " << a << " " << b << " " << c << "\n";
}
void mark() {cout << "#" << "\n";}
ll pcount(ll x) {return __builtin_popcountll(x);}
const int mod = 1e9 + 7;
//const int mod = 998244353;

int main(){
	int n,d; cin >> n >> d;
    vvl v(n,vl(2));
    two_sat ts(n);
    rep(i,n) rep(j,2) cin >> v[i][j];
    rep(i,n){
        REP(j,i+1,n){
            rep(k,2){
                rep(l,2){
                    if(abs(v[i][k] - v[j][l]) < d){
                        ts.add_clause(i,k,j,l);
                    }
                }
            }
        }
    }
    if(!ts.satisfiable()){
        cout << "No" << "\n";
        return 0;
    }
    cout << "Yes" << "\n";
    auto a = ts.answer();
    rep(i,n) cout << v[i][a[i]^1] << "\n";
}

Measured memory_bytes: 3788
import math
A = []
N = int(input())
maxdiff = 0
for n in range(N):
    A.append(int(input()))
R = tuple(A)

Dmax = R[1] -R[0]
Rmin = R[0]

for i in range(1, N):
    if R[i] >= R[i-1]:
        if R[i] - Rmin > Dmax:
            Dmax = R[i] -Rmin
    if R[i] < Rmin:
        Rmin = R[i]
#    print(R[i], Dmax, Rmin)

print(Dmax)

Measured memory_bytes: 17228
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#define swap(type ,a ,b) {type t; t=a; a=b; b=t;}
#define forN(i,n) for(i=0;i<n;i++)
#define forR(i,s,n) for(i=s;i<n;i++)
#define ll long long
#define pb(t,d,n) {t p;int i;forN(i,n){cin>>p;d.push_back(p);}}

using namespace std;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef vector<pair<int,int>> vpii;

int main(){
    int n, tmp, res=0;
    int i,j;
    vi d;
    cin >> n;
    pb(int, d, n);
    forN(i,n-1){
        forR(j,i+1,n){
            res += d[i] * d[j];
        }
    }
    cout << res << endl;
}

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

#pragma warning(disable:4996)
using namespace std;
using ld = long double;
const ld eps = 1e-9;

void out(const vector<vector<pair<int,int>>>&edges) {
	cout << 20 << " " << accumulate(edges.begin(), edges.end(), 0,
		[](const int a, const vector<pair<int,int>>&v) {return v.size() + a; })<<endl;

	for (int i = 0; i < edges.size(); ++i) {
		for (auto e : edges[i]) {
			cout<<i+1<<" "<<e.first+1<<" "<<e.second<<endl;
		}
	}
	return;
}

int main() {
	int L;cin>>L;
	vector<vector<pair<int,int>>>edges(20);

	const int start=0;
	const int goal=19;
	 int id=0;
	while (L) {
		int x=L%2;
		if (x) {
			if(L==1&&id==goal)break;
			edges[id].push_back(make_pair(goal,L-1));
			L--;
		}
		else {
			
			edges[id].push_back(make_pair(id+1,L/2));
			edges[id].push_back(make_pair(id + 1, 0));
			L/=2;
			id++;
		}
	}

	out(edges);
	return 0;
} 

Measured memory_bytes: 256
#include<bits/stdc++.h>
 
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define vi vector<int>
#define v(i) vector<i>
#define FOR(i,a,b) for(i=a;i<b;i++)
#define FORE(i,a,b) for(i=a;i<=b;i++)
#define FORV(i,a,b) for(i=a;i>b;i--)
#define FOREV(i,a,b) for(i=a;i>=b;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define look(v) for(auto c:v) cout<<c<<" "; cout<<"\n";
#define dfdc int i,j,k,m,n,ct=0;string s;
#define ppl(a,st,end) for(i=st;i<=end;i++)cin>>a[i];
#define fz(a) memset(a,0,sizeof a);
#define dp_1(n) int dp[n];fz(dp);
#define dp_2(m,n) int dp[m][n];fz(dp);
#define arpt(a,s,e) for(i=s;i<=e;i++) cout<<a[i]<<" ";cout<<"\n";
#define tk int t;cin>>t;while(t--)
 
using namespace std;
 
typedef long long int ll;
 
 
int main(){
    fastio
    float n,x,t;
    cin>>n>>x>>t;
    int ans = ceil(n/x)*t;
    cout<<ans<<"\n";
    return 0;
}

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

int main() {
    int n;
    string s;
    cin >> s;
    n = s.size();
    vector<int> ans(n);
    
    rep(ri,2){
        int cnt = 0;
        rep(i,n){
            if(s[i]=='R'){
                cnt ++;
            }else{
                ans[i] += cnt/2;
                ans[i-1] += (cnt+1)/2;
                cnt = 0;
            }
        }
        reverse(ans.begin(),ans.end());
        reverse(s.begin(),s.end());
        rep(i,n){
            if(s[i]=='R') s[i]='L';
            else s[i]='R';
        }
    }
    
    rep(i,n) {
        printf("%d\n", ans[i]);
    }
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
 
#define coutv(v) for (int i = 0; i < (v).size(); ++i) cout << v[i] << ' '; cout << endl;
#define coutvv(v) for (int i = 0; i < (v).size(); ++i) {for (int j = 0; j < (v[i]).size(); ++j) cout << v[i][j] << ' '; cout << endl;}
#define debugv(v) {for (int i = 0; i < (v).size(); ++i) cerr << v[i] << ' '; cerr << endl;}
#define debugvv(v) {for (int i = 0; i < (v).size(); ++i) {for (int j = 0; j < (v[i]).size(); ++j) cerr << v[i][j] << ' '; cerr << endl;}}
#define TC int TESTCASE; cin >> TESTCASE; while (TESTCASE--)
typedef long long ll;
 


int main() {
	string a;
	cin >> a;
	if (a == "SUN") {
		cout << 7;
	}
	if (a == "MON") {
		cout << 6;
	}
	if (a == "TUE") {
		cout << 5;
	}
	if (a == "WED") {
		cout << 4;
	}
	if (a == "THU") {
		cout << 3;
	}
	if (a == "FRI") {
		cout << 2;
	}
	if (a == "SAT") {
		cout << 1;
	}
}
 


Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<int>;
using VL = vector<ll>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);(i)++)
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);(i)--)
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);(i)--)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
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; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T> inline istream& operator>>(istream& input, vector<T>& v) { for (auto& elemnt : v)input >> elemnt; return input; }

int main() {
    init();
    
    int w;
    cin >> w;
    cout << w * 32 << "\n";
}


Measured memory_bytes: 3188
n = int(input())

pf={}
m=n
for i in range(2,int(m**0.5)+1):
    while m%i==0:
        pf[i]=pf.get(i,0)+1
        m//=i
if m>1:pf[m]=1

ans = 0

for i in pf.items():
    m = i[1]

    a = 1
    cnt = 1

    while a <= m:
        cnt += 1
        a += cnt
    
    cnt -= 1

    ans += cnt

print(ans)

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

int main(){
  char a, b;
  cin >> a >> b;
  if(a == 'H' && b == 'H') cout << 'H' << endl;
  else if(a == 'D' && b == 'H') cout << 'D' << endl;
  else if(a == 'H' && b == 'D') cout << 'D' << endl;
  else cout << 'H' << endl;
  return 0;
}

Measured memory_bytes: 256
N,K= map(int,input().split())
okashi=[0]*N

for i in range(K):
    d=int(input())
    Ad = list(map(int,input().split()))
    for j in Ad:
        okashi[j-1]+=1
count=0
for i in okashi:
    if i==0:
        count+=1
print(count)

Measured memory_bytes: 67752
#include<bits/stdc++.h>
using namespace std;
long long n,a[100010],b[100010],last,ans;
int main(){
	cin>>n;
	for (int i=0;i<=n;i++) cin>>a[i];
	for (int i=0;i<n;i++) cin>>b[i];
	last=b[0]-min(b[0],a[0]);ans+=min(a[0],b[0]);
	for (int i=1;i<=n;i++){
		ans+=min(a[i],last);a[i]-=min(a[i],last);
		last=b[i]-min(b[i],a[i]);ans+=min(a[i],b[i]);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1792
/* Akshat Sharma @akshat98 */
#include <iostream>
#include <bits/stdc++.h>
#define IOS  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define mp   make_pair
#define pb   push_back
#define F    first
#define S    second
#define ll   long long
#define MOD  1000000007
#define MAX  1000000001
#define vi   vector<int>
#define vl   vector<ll>
#define vpi  vector<pair<int,int> >
#define vpl  vector<pair<ll,ll> >
#define rep(i,a,b) for(i=a;i<b;i++)
#define reqp(i,a,b) for(i=a;i<=b;i++)
#define ren for(i=0;i<n;i++)
#define ALL(a)  (a).begin(),(a).end()
using namespace std;
typedef pair<int,int>pii;
typedef pair<ll,ll>pll;


int main()
{

	int i,j,k,l,n,test_case,m,r;
	test_case=1;
	//cin>>test_case;
	while(test_case--){
		cin>>n;
		string str;
		cin>>str;
		ll ans=0;
		int rc=0,bc=0,gc=0;
		for(auto it:str){
			if(it=='R'){
				ans+=(gc*bc);
				rc++;
			}else if(it=='G'){
				ans+=(rc*bc);
				gc++;
			}else{
				ans+=(gc*rc);
				bc++;
			}
		}	
		// cout<<ans<<"\n";	
		rep(i,1,n-1){
			rep(j,1,i+1){
				if(i+j>=n)break;
				if(str[i-j]==str[i]|| str[i-j]==str[j+i]|| str[i]==str[i+j]){
					;
				}else{
					ans--;
				}
			}
		}



		cout<<ans<<"\n";


	}
	
	return 0;
}

Measured memory_bytes: 3632
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <iomanip>
using namespace std;
#define INF 1e9
#define PI acos(-1)
typedef long long ll;



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

	int n = str.size()-1;

	vector<ll> num;

	for (int i = 0; i < (1<<n); i++) {//2^nの全通り
		ll S=0;
		int left = 0;
		for (int k = 0; k < n; k++) {//桁数
			if ((i & (1 << k))) {
				string sub = str.substr(left, k - left + 1);
				S += stoll(sub);
				left = k+1;
			}
		}
		string sub = str.substr(left, n - left+1);
		S += stoll(sub);

		num.push_back(S);
	}

	ll ans = 0;

	for (int i = 0; i < (1<<n); i++) {
		ans += num[i];
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
using namespace std;
template <class T>
inline bool read(T &ret)
{
    char c;
    int sgn;
    if(c=getchar(),c==EOF)
        return 0; //EOF
    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;
}
const int INF=0x3f3f3f3f;
const int MAXN=2000010;
struct qnode
{
    int v;
    int c;
    qnode(int _v=0,int _c=0):v(_v),c(_c) {}
    bool operator <(const qnode &r)const
    {
        return c>r.c;
    }
};
struct Edge
{
    int v,cost;
    Edge(int _v=0,int _cost=0):v(_v),cost(_cost) {}
};
vector<Edge>E[MAXN];
bool vis[MAXN];
int dist[MAXN];
void Dijkstra(int start,int n)//点的编号从1开始
{
    memset(vis,false,sizeof(vis));
    for(int i=1; i<=n; i++)
        dist[i]=INF;
    priority_queue<qnode>que;
    while(!que.empty())
        que.pop();
    dist[start]=0;
    que.push(qnode(start,0));
    qnode tmp;
    while(!que.empty())
    {
        tmp=que.top();
        que.pop();
        int u=tmp.v;
        if(vis[u])
            continue;
        vis[u]=true;
        for(int i=0; i<E[u].size(); i++)
        {
            int v=E[tmp.v][i].v;
            int cost=E[u][i].cost;
            //cout<<u<<' '<<v<<' '<<cost<<endl;
            if(!vis[v]&&dist[v]>dist[u]+cost)
            {
                dist[v]=dist[u]+cost;
                que.push(qnode(v,dist[v]));
            }
        }
    }
}
void addedge(int u,int v,int w)
{
    E[u].push_back(Edge(v,w));
    E[v].push_back(Edge(u,w));
}
#define pr pair<int,int>
#define mp make_pair
map<pr,int> V;
int cnt;
int GetId(int u,int c)
{
    if(V.find(mp(u,c)) != V.end())
        return V[mp(u,c)];
    return V[mp(u,c)] =++ cnt;
}
int main()
{

    int n,m;
    while(scanf("%d%d",&n,&m) != EOF)
    {
        V.clear();
        for(int i = 1;i<=n*8;i++) E[i].clear();
        cnt = n;
        int u,v,c;
        for(int i = 0; i<m; i++)
        {
            read(u),read(v),read(c);
            int uu = GetId(u,c);
            int vv = GetId(v,c);
            //cout<<uu<<' '<<vv<<endl;
            addedge(uu,vv,0);
            addedge(u,uu,1);
            addedge(v,vv,1);
        }
        Dijkstra(1,cnt);
//    for(int i = 1;i<=cnt;i++)
//    {
//        cout<<dist[i]<<endl;
//    }
        if(dist[n] == INF)
            printf("-1\n");
        else
            printf("%d\n",dist[n]/2);
    }


    return 0;
}


Measured memory_bytes: 97020
// in case of multiple test cases and N=1e5 don't intialize arrays as global except for graph vector-array
// always check whether or not you are doing mod of a negative number
// always use 1LL instead of 1
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
 
using namespace __gnu_pbds;
using namespace std;

#define double      	long double
#define int         	long long
#define pb          	push_back
#define pii         	pair<int,int>
#define vi          	vector<int>
#define vii         	vector<pii>
#define mi          	map<int,int>
#define mii         	map<pii,int>
#define all(a)      	(a).begin(),(a).end()
#define sz(x)       	(int)x.size()
// just comment the line below in case of interactive problems
#define endl        	"\n"
#define repp(i,a,b) 	for(int i=a;i<b;i++)
#define rep(i,a,b) 		for(int i=a;i<=b;i++)
#define brep(i,a,b)     for(int i=a;i>=b;i--)
#define deb1(x)      	cout << #x << "=" << x << endl
#define deb2(x, y)  	cout << #x << "=" << x << "," << #y << "=" << y << endl
#define deb3(x, y, z)  	cout << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define trace(v) 		for(auto it=v.begin();it!=v.end();it++)cout<<*it<<" ";cout<<endl;
#define tracearr(a,l,r) for(int iii=l;iii<=r;iii++)cout << a[iii] << " ";cout << endl;
#define PI          	3.1415926535897932384626
#define F 				first
#define S 				second
#define clr(x,y) 		memset(x, y, sizeof(x))
#define IOS         	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);


typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
// *s.find_by_order(1) - gives the 2nd samllest element in set
// s.order_of_key(x)   - gives the number of elements in the set which are strictly smaller than x


const int N=1e5 + 5;
const int MOD=1e9 + 7;

int32_t main()
{
	IOS;
	int T=1;
	//cin >> T;
	// int numOfSetBits = __builtin_popcountll(n);
	std::cout << std::fixed << std::setprecision(12);
	while(T--)
	{
		string s;
		cin >> s;
		int sum = 0;
		for(char c: s)
		{
			int x = c-'0';
			sum += x;
		}
		if(sum%9==0)
			cout << "Yes";
		else
			cout << "No";
	}
}

Measured memory_bytes: 3732
import java.util.*;

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

             for(int i=1; ; i++) {
		int x = sc.nextInt();
		if(x==0) {
		    break;
		}
        	System.out.println("Case "+i+": "+x);
             }
         }
}


Measured memory_bytes: 42204
#include <iostream>
#include <cstdint>
#include <algorithm>

int const MAXN = 3000;

int N, a[MAXN];

int64_t dp[2][MAXN];

int main() {
  std::cin >> N;
  for(int i = 0; i < N; ++i) std::cin >> a[i];

  for(int i = 0; i <=N; ++i) dp[0][i] = 0;
  for(int i = 1; i <=N; ++i) for(int j = 0; j+i<=N; ++j) {
    int k = j+i;
    dp[i%2][j] = std::max(a[k-1] - dp[(i-1)%2][j], a[j] - dp[(i-1)%2][j+1]);
  }
  std::cout << dp[N%2][0] << std::endl;
  return 0;
}


Measured memory_bytes: 256
n,k=input().split()
n=int(n)
k=int(k)
i=0
ii=0
ans=0.0
while i!=n:
    i=i+1
    j=i
    ii=0
    anss=1
    while j<k:
       j=j*2
       ii=ii+1
       anss=anss*1/2

    ans=ans+anss
ans=ans/n
print(ans)

Measured memory_bytes: 3060
A = int(input())
B = int(input())
C = int(input())
X = int(input())

pattern = 0
for ai in range(A+1):
    for bi in range(B+1):
        for ci in range(C+1):
            if X == 500 * ai + 100 * bi + 50 * ci:
                pattern = pattern + 1
print(pattern)

Measured memory_bytes: 3060
// AOJ DSL_4_A Union of Rectangles
// 2018.5.15 bal4u

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#if 1
#define gc() getchar_unlocked()
#else
#define gc() getchar()
#endif
int in()
{
	int n = 0, c = gc();
	if (c == '-') {	c = gc();
		do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
		return -n;
	}
	do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
	return n;
}

#define MAX_N 2005
#define MAX   4005

int x1[MAX_N], y1[MAX_N], x2[MAX_N], y2[MAX_N];
int x[MAX], xs;
int y[MAX], ys;
short s[MAX][MAX];

int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; }

int uniq(int *a, int n)
{
	int i, j;
	
	for (i = 0, j = 1; j < n; j++) {
		while (j < n && a[j] == a[i]) j++;
		if (j < n) if (++i != j) a[i] = a[j];
	}
	return i+1;
}

int main()
{
	int N, i, r, c, r1, c1, r2, c2;
	int lo, hi, mi;
	long long ans;

	N = in(); xs = ys = 0;
	for (i = 0; i < N; i++) {
		x1[i] = c = in(), y1[i] = r = in();
		x[xs++] = c, y[ys++] = r;
		x2[i] = c = in(), y2[i] = r = in();
		x[xs++] = c, y[ys++] = r;
	}
	qsort(x, xs, sizeof(int), cmp); xs = uniq(x, xs);
	qsort(y, ys, sizeof(int), cmp); ys = uniq(y, ys);

	for (i = 0; i < N; i++) {
		lo = 0, hi = xs;
		while (lo < hi) {
			mi = (lo + hi) >> 1;
			if (x[mi] < x1[i]) lo = mi + 1; else hi = mi;
		}
		c1 = lo;
		
		lo++, hi = xs;
		while (lo < hi) {
			mi = (lo + hi) >> 1;
			if (x[mi] < x2[i]) lo = mi + 1; else hi = mi;
		}
		c2 = lo;
		
		lo = 0, hi = ys;
		while (lo < hi) {
			mi = (lo + hi) >> 1;
			if (y[mi] < y1[i]) lo = mi + 1; else hi = mi;
		}
		r1 = lo;
		
		lo++, hi = ys;
		while (lo < hi) {
			mi = (lo + hi) >> 1;
			if (y[mi] < y2[i]) lo = mi + 1; else hi = mi;
		}
		r2 = lo;

		s[r1][c1]++, s[r1][c2]--;
		s[r2][c1]--, s[r2][c2]++;
	}

	for (r = 0; r < ys; r++) for (c = 1; c < xs; c++) s[r][c] += s[r][c-1];
	for (r = 1; r < ys; r++) for (c = 0; c < xs; c++) s[r][c] += s[r-1][c];

	ans = 0;
	for (r = 0; r < ys; r++) for (c = 0; c < xs; c++) {
		if (s[r][c]) {
			c1 = c;
			while (s[r][c]) c++;
			ans += (long long)(x[c]-x[c1])*(y[r+1]-y[r]);
		}
	}
	printf("%lld\n", ans);
	return 0;
}



Measured memory_bytes: 33156
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    int a[n+1];
    int sub[n+1];
    memset(sub,0,sizeof(sub));
    for(int i = 2; i <= n ;i++ )cin >> a[i];
    for(int i = 2; i<= n; i++)sub[a[i]]++;
    for(int i = 1 ;i <= n;i++)cout<<sub[i]<<"\n";
}

Measured memory_bytes: 5156
import Data.List

l1 = [ "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z" ]
l2 = ["ld", "mb", "mp", "nc", "nd", "ng", "nt", "nw", "ps", "qu", "cw", "ts"]

-- |
-- >>> nw "abc"
-- ("a","bc")
-- >>> nw "ncw"
-- ("nc","w")
nw (a:[]) = ([a],[])
nw (a:b:x) = if elem [a,b] l2 then ([a,b],x) else ([a],(b:x))

splt [] = []
splt w =
  let (l,r) = nw w
  in
    l:(splt r)

g l (a:[]) = []
g l (a:b:x) =
  let n = g l (b:x)
  in
    if l == a then (b:n) else n

c (w1,n1) (w2,n2) =
  let i1 = elemIndex w1 (l1++l2)
      i2 = elemIndex w2 (l1++l2)
      cn = compare n1 n2
      ci = compare i2 i1
  in
    if cn /= EQ then cn else ci

f s l =
  let t = p $ sort $ concat $ map (g l) s
      m = maximumBy c t
  in
    if t == []
    then unwords [l, "a 0"]
    else unwords [l, fst m, show $ snd m]


p [] = []
p l@(a:_) =
  let n = length $ takeWhile (== a) l
      r = dropWhile (== a) l
  in
    (a,n):(p r)

ans c =
  let pl = map splt $ words c
      ct = map (f pl) (l1++l2)
  in
    ct

main = do
  _ <- getLine
  c <- getContents
  let o = ans c
  mapM_ putStrLn o



Measured memory_bytes: 10212
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
n,q=map(int,input().split())
ab=[[int(i) for i in input().split()] for j in range(n-1)]
px=[[int(i) for i in input().split()] for j in range(q)]

graph=[[] for i in range(n+1)]
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)
    
value=[0]*(n+1)

for p,x in px:
    value[p]+=x
    
q=[(0,1)]
while q:
    parent,child = q.pop()
    value[child]+=value[parent]
    for i in graph[child]:
        if i==parent:
            continue
        q.append((child,i))
ans=' '.join(map(str,value[1:]))
print(ans)
    

Measured memory_bytes: 124240
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
    string s;
    ll k;
    cin >> s >> k;

    for(int i = 0; i < k && i < s.size(); i++)
    {
        if(s[i] == '1')
        {
            continue;
        }
        else
        {
            cout << s[i] << endl;
            return 0;
        }
    }
    ll a4 = s.size();
    cout << s[min(a4, k)-1] << endl;
}


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

#define debug(x) cerr<<#x<<'='<<x<<endl
#define set0(x) memset(x,0,sizeof(x))
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
template<typename T> void read(T &x){
	x = 0;char ch = getchar();ll f = 1;
	while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
	while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
int mod = 998244353;
inline int mul(int x,int y){return 1ll*x*y%mod;}
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int sub(int x,int y){return x-y<0?x-y+mod:x-y;}
inline int sq(int x){return 1ll*x*x%mod;}
int mpow(int a,int b){return b == 0 ? 1 : ( b&1 ? mul(a,sq(mpow(a,b/2))) : sq(mpow(a,b/2)));}

const int N = 1000000;
int fac[N+10],invfac[N+10],n,k;

int C(int n,int m){
	if(n<0 || m<0 || m>n)return 0;
	return mul(fac[n],mul(invfac[m],invfac[n-m]));
}
void init_C(){
	fac[0] = 1;
	for(int i=1;i<=N;i++)fac[i] = mul(fac[i-1],i);
	invfac[N] = mpow(fac[N],mod-2);
	for(int i=N-1;i>=0;i--) invfac[i] = mul(invfac[i+1],i+1);
}

int main() {
	init_C();
	ll n,a,b,k;
	cin>>n>>a>>b>>k;
	int ans  = 0;
	for(int i=0;i<=n;i++){
		if(i*a>k || (k-i*a)%b!=0)continue;
		ll bc = (k-i*a)/b;
		ans = add(ans,mul(C(n,i),C(n,bc)));
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 8064