akhauriyash/Code-Regression huggingface dataset:
import std.algorithm;
import std.conv;
import std.stdio;
import std.string;

void main()
{
	auto hw = readln.split.map!( to!byte );
	auto s = new string[ hw[ 0 ] ];
	foreach( ref sl; s )
	{
		sl = readln.strip;
	}
	
	writeln( solve( hw[ 0 ], hw[ 1 ], s ) );
}

string solve( in byte h, in byte w, in string[] s )
{
	bool[][] r;
	
	r.length = h;
	foreach( ref rl; r )
	{
		rl.length = w;
	}
	
	foreach( y; 0 .. h )
	{
		foreach( x; 0 .. w )
		{
			if( s[ y ][ x ] == '#' )
			{
				if( y + 1 < h && s[ y + 1 ][ x ] == '#' )
				{
					r[ y + 1 ][ x ] = true;
					r[ y ][ x ] = true;
				}
				if( x + 1 < w && s[ y ][ x + 1 ] == '#' )
				{
					r[ y ][ x + 1 ] = true;
					r[ y ][ x ] = true;
				}
				if( r[ y ][ x ] == false ) return "No";
			}
		}
	}
	
	return "Yes";
}

unittest
{
	assert( solve( 3, 3, [ ".#.", "###", ".#." ] ) == "Yes" );
	assert( solve( 5, 5, [ "#.#.#", ".#.#.", "#.#.#", ".#.#.", "#.#.#" ] ) == "No" );
	assert( solve( 11, 11, [ "...#####...", ".##.....##.", "#..##.##..#", "#..##.##..#", "#.........#", "#...###...#", ".#########.", ".#.#.#.#.#.", "##.#.#.#.##", "..##.#.##..", ".##..#..##." ] ) == "Yes" );
	assert( solve( 4, 3, [ "##.", ".##", "##.", ".##" ] ) == "Yes" );
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef queue<ll> ql;
typedef deque<ll> dql;
typedef priority_queue<ll, vl/*, greater<ll>*/> pql; //降順(/*昇順*/)
typedef set<ll> sl;
typedef pair<ll, ll> pl;
typedef vector<vl> vvl;
typedef vector<pl> vpl;
#define rep(i, n) for(ll i = 0; i < ll(n); ++i)
#define rep2(i, n) for(ll i = 1; i <= ll(n); ++i)
//#define rep(i, k, n) for(ll i = k-1; i < ll(n); ++i)
//#define rep2(i, k, n) for(ll i = k; i <= ll(n); ++i)
#define all(v) (v).begin(), (v).end()
bool chmin(ll &a, ll b) {if(b < a) {a = b; return 1;} return 0;}
bool chmax(ll &a, ll b) {if(b > a) {a = b; return 1;} return 0;}
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
const ll MAX = 1e9;
const char newl = '\n';

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

  ll h, n, sum=0;
  cin >> h >> n;
  vl a(n);
  rep(i, n) {cin >> a[i]; sum += a[i];}
  cout << (h<=sum ? "Yes" : "No") << newl;
  return 0;
}

Measured memory_bytes: 1024
'use strict'

function main(input) {

    let ans = 'AGC'

    input = Number(input)
    if (input < 1200){
        ans = "ABC"
    }else if(input < 2800){

        ans = "ARC"
    }
    console.log(ans)

}

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

Measured memory_bytes: 11468
//accumulative sum
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;
int main()
{
	int N, K;
	string s;	
	cin >> N >> K;
	cin >> s;
	vector<int> nums;
	int now = 1, cnt = 0;
	for(char& c : s)
	{
		if(c == char(now + '0')) cnt++;
		else
		{
			nums.emplace_back(cnt);
			cnt = 1;
			now ^= 1;
		}
	}
	if(cnt != 0) nums.emplace_back(cnt);

	if(nums.size() % 2 == 0) nums.emplace_back(0);
	int length = K * 2 + 1;

	int left = 0, right = 0;
	int sum = 0, ans = 0;
	for(int i = 0; i < nums.size(); i += 2)
	{
		int nextL = i;
		int nextR = min(nextL + length, (int)nums.size());
		while(left < nextL)
		{
			sum -= nums[left];
			left++;
		}
		while(right < nextR)
		{
			sum += nums[right];
			right++;
		}
		ans = max(ans, sum);
	}

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

Measured memory_bytes: 1020
#include <stdio.h>
#include<string.h>
int main()
{
    int unant,ant,poi,count=0,flag=0;
    scanf("%d %d %d",&unant,&ant,&poi);
    while(poi>0 &&ant>0)
    {
        poi--;
        count++;
        ant--;
        count++;
    }
    if(poi>0)
    {
        while(poi>0&&unant>0)
        {
            poi--;
            unant--;
            count++;
        }
        if(poi>0) printf("%d",++count);
        else printf("%d",count);
    }
    else if(ant>0)
    {
        while(ant>0)
        {
            ant--;
            count++;
        }
    printf("%d",count);
    }
    else if(poi==0&&ant==0)printf("%d",count);
}


Measured memory_bytes: 128
"""
N = list(map(int,input().split()))
S = [str(input()) for _ in range(N)]
S = [list(map(int,list(input()))) for _ in range(h)] 
print(*S,sep="")
"""

import sys
sys.setrecursionlimit(10**6)
input = lambda: sys.stdin.readline().rstrip()
inf = float("inf") # 無限

a,b = map(int,input().split())
if 0<a<10 and 0<b<10:
    print(a*b)
else:
    print(-1)

Measured memory_bytes: 3060
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

static class Program
{
    static int Solve(long N)
    {
        var set = new HashSet<long> { N };
        if (N > 2) { set.Add(N - 1); }
        for (long i = 2; i * i <= N - 1; ++i)
        {
            if ((N - 1) % i == 0)
            {
                set.Add(i);
                if (i * i < N - 1) { set.Add((N - 1) / i); }
            }
        }
        for (long i = 2; i * i <= N; ++i)
        {
            long n = N;
            while (n % i == 0) { n /= i; }
            if (n % i == 1) { set.Add(i); }
        }
        return set.Count;
    }

    static void Main(string[] args)
    {
        long N = long.Parse(Console.ReadLine());
        Console.WriteLine(Solve(N));
    }
}


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

int main() {
	int A, B;
	cin >> A >> B;
	cout << "100 100" << endl;
	for (int i = 0;i < 50;i ++) {
		for (int j = 0;j < 100;j ++) {
			if (i % 2 == 1 || j % 2 == 0 || A <= 1) cout << "#";
			else {
				cout << ".";
				A --;
			}
		}
		cout << endl;
	}
	for (int i = 0;i < 2;i ++) {
		for (int j = 0;j < 100;j ++) {
			cout << ".";
		}
		cout << endl;
	}
	for (int i = 0;i < 48;i ++) {
		for (int j = 0;j < 100;j ++) {
			if (i % 2 == 1 || j % 2 == 0 || B <= 1) cout << ".";
			else {
				cout << "#";
				B --;
			}
		}
		if (i < 47) cout << endl;
	}
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり

まず、一つの例として格子形を考える
これを条件を満たすように表示すれば良いのでは
次のような配置を考える
.#.#.#.#.
#########
.#.#.#.#.
#########
.#.#.#.#.
…
.#.#.#.#.
#########
.........
.........
.........
#.#.#.#.#
…
.........
#.#.#.#.#
.........
#.#.#.#.#
上のパターンを100x50個、上のパターンを100x50個作ると、黒が1+25x50=1001個、白も同じ個数ある
そして、上側の白は埋めると白が1個減るが黒は減らない
下側の黒は埋めると黒が1個減るが白は減らない
これで解けるな！
*/

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {

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

		int N = sc.nextInt();
		int K = sc.nextInt();

		int[] balls = new int[N + 1];
		for (int i = 0; i < N; i++) {
			balls[sc.nextInt()]++;
		}
		int shuruiherasu = balls.length - K;
		if (shuruiherasu - K <= 0) {
			System.out.println(0);
			return;
		}
		Arrays.parallelSort(balls);
		int sum = 0;
		for (int i = 0; i < shuruiherasu; i++) {
			sum += balls[i];
		}
		System.out.println(sum);

	}
}


Measured memory_bytes: 76924
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstring>
#include <queue>
using namespace std;

#define rep(i,n) for(int i=0; i<n; i++)
typedef long long ll;
typedef pair<int,int> pii;

struct node {
	int p, t, m;
	node(int pp, int tt, int mm) {
		p = pp;
		t = tt;
		m = mm;
	}
};

bool operator<(const node& lhs, const node& rhs) {
	return lhs.t > rhs.t;
}

vector<pii> cost[100];
bool visit[100][101];

int main() {
	int n, m, l, k, a, h;
	while(cin >> n >> m >> l >> k >> a >> h, n) {
		memset(visit, 0, sizeof(visit));
		bool bld[100]={};
		rep(i,l) {
			int x;
			cin >> x;
			bld[x] = true;
		}
		bld[h] = bld[a] = true;
		rep(i,n) cost[i].clear();
		rep(i,k) {
			int x, y, t;
			cin >> x >> y >> t;
			if( t <= m ) {
				cost[x].push_back(pii(y,t));
				cost[y].push_back(pii(x,t));
			}
		}
		priority_queue<node> que;
		que.push(node(a,0,m));
		bool found = false;
		while(!que.empty()) {
			node nd = que.top();
			que.pop();
			if( nd.p == h ) {
				found = true;
				cout << nd.t << endl;
				break;
			}
			if( visit[nd.p][nd.m] ) continue;
			visit[nd.p][nd.m] = true;
			if(bld[nd.p]) {
				for(int nm=nd.m+1; nm<=m; nm++) {
					if( !visit[nd.p][nm] ) {
						que.push( node(nd.p, nd.t+nm-nd.m, nm) );
					}
				}
			}
			rep(i,cost[nd.p].size()) {
				int nm = nd.m-cost[nd.p][i].second;
				if( nm >= 0 && !visit[cost[nd.p][i].first][nm] ) {
					que.push(node(cost[nd.p][i].first, nd.t+cost[nd.p][i].second, nm));
				}
			}
		}
		if(!found) {
			cout << "Help!" << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 2700
mod = 998244353

n, s = map(int, input().split())
a = list(map(int, input().split()))

a.sort()

while a[-1] > s:
    a.pop(-1)
    if a == []:
        print(0)
        exit()

su = sum(a)
if su < s:
    print(0)
    exit()
if su == s:
    print(pow(2, n - len(a), mod))
    exit()

dp = [0] * (s + 1)
dp[0] = 1
for i in a:
    newdp = [2 * j for j in dp]
    for j in range(s - i + 1):
        newdp[j+i] += dp[j]
    dp = newdp

print(dp[s] * pow(2, n - len(a), mod) % mod)

Measured memory_bytes: 183616
#include<cstdio>

int N,M,K[1000];
int C[200],T[200];

int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<M;i++){
        scanf("%d",K+i);
    }
    
    for(int i=0;i<2*N;i++) C[i]=i+1;

    for(int j=0;j<M;j++){
        if(K[j]==0){
            for(int i=0;i<2*N;i++)T[i]=C[i];
            for(int i=0;i<N;i++)C[i*2]=T[i];
            for(int i=0;i<N;i++)C[i*2+1]=T[i+N];
        }else{
            for(int i=0;i<2*N;i++)T[i]=C[i];
            for(int i=0;i<K[j];i++)C[2*N-K[j]+i]=T[i];
            for(int i=0;i<2*N-K[j];i++)C[i]=T[K[j]+i];                                             
        }                                                                                          
    }                                                                                              
                                                                                                   
    for(int i=0;i<2*N;i++){                                                                        
        printf("%d\n",C[i]);                                                                       
    }                                                                                              
}      

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

int kosuu(int m){
	int c = 0;
	for(int i=1; i<=m; i++){
		if(m%i == 0) c++;
	}
	return c;
}
int main(){
	int n, c = 0;
	cin >> n;
	for(int i=1; 2*i-1<=n; i++){
		int m = 2*i-1;
		if(kosuu(m) == 8) c++;
	}
	cout << c << endl;
}

Measured memory_bytes: 256
N,x = map(int, input().split())
A = [int(i) for i in input().split()]
A.sort()
c = 0
for i in range(N):
    x -= A[i]
    if x >= 0:
        c += 1
    if x <= 0:
        print(c)
        break
else:
    print(N - 1)

Measured memory_bytes: 9036
import string
N = int(input())
S = input()
ascii_uppercase = list('ABCDEFGHIJKLMNOPQRSTUVWXYZ')
for s in S:
    s_index = ascii_uppercase.index(s)
    ans_index = (s_index + N) % len(ascii_uppercase)
    print(ascii_uppercase[ans_index], end="")


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

int main(){
    //input
    int N, K;
    cin >> N >> K;
    long long a[N+1];
    int i, j;
    for(i = 1; i <= N; i++){
        cin >> a[i];
    }

    //calc
    long long costmin = 100000000000, cost;
    int reform;
    long long heightmax[N+1], heightmaxcopy[N+1], height_after_reform;
    heightmax[1] = a[1];
    for(i = 2; i <= N; i++){
        heightmax[i] = max(a[i],heightmax[i-1]);
    }
    int bit;
    for(bit = 0; bit < (1<<(N-1)); bit++){
        cost = 0;
        reform = 0;
        for(i = 0; i < N-1; i++){
            reform += ((bit>>i) & 1);
        }
        if(reform != K-1) continue;
        for(i = 1; i <= N; i++){
            heightmaxcopy[i] = heightmax[i];
        }
        for(i = 2; i <= N; i++){
            if(!((bit>>(i-2)) & 1)) continue;
            height_after_reform = max(heightmaxcopy[i-1]+1,a[i]);
            cost += height_after_reform - a[i];
            heightmaxcopy[i] = height_after_reform;
            for(j = i+1; j <= N; j++){
                heightmaxcopy[j] = max(a[j],heightmaxcopy[j-1]);
            }
        }
        if(costmin > cost){
            costmin = cost;
        }
    }
    if(costmin == 100000000000){
        costmin = 0;
    }

    //answer
    cout << costmin << endl;
    system("pause");
    return 0;
}

Measured memory_bytes: 504
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#include <vector>
using namespace std;
typedef long long LL;

LL cnt[20005] = {0},P,now = 0,ans = 0,n;
string s;

LL kpw(LL x,LL y){
	LL ans = 1,tmp = x % P;
	while(y){
		if(y & 1) ans = (ans * tmp) % P;
		tmp = (tmp * tmp) % P;
		y >>= 1;
	}
	return ans;
}

int main(){
	ios::sync_with_stdio(false);
	cin >> n >> P;
	cin >> s; s = ' ' + s;
	
	if(P == 2){
		for(LL i = 1;i <= n;i ++){
			if((s[i] - '0') % 2 == 0) ans += i;
		}
		cout << ans << endl;
		return 0;
	}
	
	if(P == 5){
		for(LL i = 1;i <= n;i ++){
			if((s[i] - '0') % 5 == 0) ans += i;
		}
		cout << ans << endl;
		return 0;
	}
	
	cnt[0] ++;
	for(LL i = n;i >= 1;i --){
		now = (now + ((LL)(s[i] - '0')) * kpw(10,(n - i))) % P;
		ans += cnt[now]; cnt[now] ++;
	}
	cout << ans << endl;
	return 0;
}
//

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

void solve()
{
  char a,b;
  cin >> a >> b;
  if(a == 'H') {
    if(b == 'H') {
      cout << 'H' << endl;
    } else if(b == 'D') {
      cout << 'D' << endl;
    }
  } else if(a == 'D') {
    if(b == 'H') {
      cout << 'D' << endl;
    } else if(b == 'D') {
      cout << 'H' << endl;
    }
  }
}

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long n, a[200100], i, b[200100], pre, back;
    cin >> n;
    pre=0;back=n-1;
    for(i=0;i<n;i++){
        cin >> a[i];
        }
        reverse(a, a+n);
    for(i=0;i<n;i++){
        if(i%2==0){
            b[pre]=a[i];
            pre++;
        }
        else {
            b[back]=a[i];
            back--;
        }
    }

    for(i=0;i<n;i++){
        cout << b[i] << " ";
    }
    cout <<endl;

    return 0;
}

Measured memory_bytes: 6760
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-9;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

int n;
vi a,b;

int main(){
	cin>>n;
	a=b=vi(n);
	for(int i=0;i<n;i++) cin>>a[i];
	for(int i=0;i<n;i++) cin>>b[i];
	vvi dp(1<<n,vi(n,inf));
	for(int i=0;i<n;i++) dp[1<<i][i]=0;
	for(int i=0;i<1<<n;i++) for(int j=0;j<n;j++) if(dp[i][j]<inf){
		int t=0,pre;
		for(int k=0;k<n;k++) if(i&1<<k) t++;
		if((abs(t-j))%2==1) pre=a[j];
		else pre=b[j];
		int tmp=t;
		for(int k=0;k<n;k++){
//			cout<<pre<<' '<<t<<' '<<k<<' '<<((abs(t-k))%2==0?a[k]:b[k])<<endl;
			if(!(i&1<<k)&&pre<=((abs(tmp-k))%2==0?a[k]:b[k])){
				int I=i+(1<<k);
//				if(I==5&&k==0) cout<<i<<' '<<j<<endl;
				dp[I][k]=min(dp[I][k],dp[i][j]+t);
			}
			if(i&1<<k) t--;
		}
//		cout<<i<<' '<<j<<' '<<dp[i][j]<<' '<<pre<<endl;
	}
	int res=inf;
	for(int i=0;i<n;i++) res=min(res,dp[(1<<n)-1][i]);
	if(res==inf) res=-1;
	cout<<res<<endl;
}

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

using namespace std;

const int MAX = 1e5 + 10;
const int CRT = 2200;

vector<int> lp(MAX, 0);
vector<long long> pr;

void init() {
  for(int i = 2; i < MAX; i++) {
    if(!lp[i]) {
      pr.push_back((long long) i);
      for(int j = 2 * i; j < MAX; j += i) {
        lp[j] = 1;
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  init();
  int n;
  cin >> n;
  vector<long long> a(n);
  map<vector<pair<long long, int>>, int> mp;
  int ans = 0;
  for(int i = 0; i < n; i++) {
    cin >> a[i];
    vector<pair<long long, int>> Vp;
    for(int j = 0; j < MAX && pr[j] < CRT; j++) {
      int cn = 0;
      while(a[i] % pr[j] == 0) {
        cn++;
        a[i] /= pr[j];
      }
      cn %= 3;
      if(cn) Vp.push_back({pr[j], cn});
    }
    if(a[i] != 1) {
      if(a[i] < MAX && lp[a[i]] == 0) {
        Vp.push_back({a[i], 1});
        a[i] = 1;
      }
      else {
        long long msrt = sqrt(a[i]);
        if(msrt * msrt == a[i]) {
          Vp.push_back({msrt, 2});
          a[i] = 1;
        }
      }
    }
    if(a[i] != 1) ans++;
    else {
      mp[Vp]++;
    }
  }
  for(auto it = mp.begin(); it != mp.end(); it++) {
    int cnt1 = (*it).second, cnt2 = 0;
    if(cnt1 != 0) {
      vector<pair<long long, int>> Vp = (*it).first;
      if(Vp.size() == 0) {
        ans++;
        continue;
      }
      for(int i = 0; i < (int) Vp.size(); i++) {
        Vp[i].second = 3 - Vp[i].second;
      }
      auto it2 = mp.find(Vp);
      if(it2 != mp.end()) {
        cnt2 = (*it2).second;
        (*it2).second = 0;
      }
      ans += max(cnt1, cnt2);
    }
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 12672
#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define For(i, a, b) for (int i = int(a); i < int(b); i++)
#define Dor(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define Foz(i, a) For(i, 0, a)
#define Doz(i, a) Dor(i, 0, a)
#define Trav(e, v) for (auto& e : v)
#define pb push_back
#define mp make_pair
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vii = vector<ii>;
template <typename T> bool ckmin (T& a, T b) { return (b < a) ? a = b, 1 : 0; }
template <typename T> bool ckmax (T& a, T b) { return (b > a) ? a = b, 1 : 0; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#ifdef XVENOM
	#define errp(...) fprintf(stderr, __VA_ARGS__)
	#define dbg(...) errp("[%s]: ", #__VA_ARGS__), dbg_str(__VA_ARGS__)
#else
	#define errp(...)
	#define dbg(...)
#endif
template <typename U, typename V> string to_string (pair<U, V>);
string to_string (string& e) { return "\"" + e + "\""; }
string to_string (char e) { return "\'" + string(1, e) + "\'"; }
string to_string (bool e) { return e ? "true" : "false"; }
template <typename T> string to_string (T e) {
	string s = "[ ";
	for (auto& x : e) s += to_string(x) + " ";
	return s + "]";
}
template <typename U, typename V> string to_string (pair<U, V> e) {
	return "(" + to_string(e.first) + ", " + to_string(e.second) + ")";
}
void dbg_str () { errp(" \n"); }
template <typename U, typename... V> void dbg_str (U u, V... v) {
 	errp(" %s", to_string(u).c_str()); dbg_str(v...);
}
/* --- */
using iii = tuple<int, int, int>;
const int N = 110;
const int INF = (int)1e9;
int sp[N][N], n, m;
vector<iii> edges;

bool check (int k) {
	int a = get<0>(edges[k]), b = get<1>(edges[k]), w = get<2>(edges[k]);
	Foz(i, n) Foz(j, n) if (i != j) {
		if (sp[i][a] + w + sp[b][j] == sp[i][j]) return false; 
	}
	return true;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	/* --- */
	cin >> n >> m;
	int a, b, c;
	Foz(i, n) Foz(j, n) sp[i][j] = INF;
	Foz(i, m) {
		cin >> a >> b >> c;
		a--; b--;
		sp[a][b] = sp[b][a] = c;
		edges.pb(make_tuple(a, b, c));
	}
	
	Foz(i, n) sp[i][i] = 0;
	Foz(k, n) Foz(i, n) Foz(j, n) ckmin(sp[i][j], sp[i][k] + sp[k][j]);
	
	int ans = 0;
	Foz(i, m) {
		int x = check(i);
		ans += x;
	}
	cout << ans << '\n';
		
}



Measured memory_bytes: 384
A, B, C, D = list(map(int, input().split()))

def gcd(x, y):
  b = max(x, y)
  s = min(x, y)
  r = b % s
  while r != 0:
    b = s
    s = r
    r = b % s
  return s

def lcm(x, y):
  return (x * y) // gcd(x,y)

E = lcm(C, D)

def div(X):
  return X - ((X // C) + (X // D)) + (X // E)

print(div(B) - div(A - 1))

Measured memory_bytes: 3064
#include <iostream>

using namespace std;

int main(){
    int n,a,b;
    cin>>n>>a>>b;
    int maxi = min(a,b);
       cout<<maxi<<endl;
    if(n<=a+b){
        int mini = a+b-n;
        cout<<mini<<endl;
    }else{
        int mini = 0;
        cout<<mini<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
while 1:
    d, w = map(int, input().split())
    if d == w == 0:
        break
    E = [list(map(int, input().split())) for i in range(d)]
    ans = 0
    for x2 in range(d):
        for y2 in range(w):
            for x1 in range(x2-1):
                for y1 in range(y2-1):
                    co = 10**18
                    for x in range(x1, x2+1):
                        co = min(co, E[x][y1], E[x][y2])
                    for y in range(y1, y2+1):
                        co = min(co, E[x1][y], E[x2][y])
                    ci = cnt = 0
                    for x in range(x1+1, x2):
                        for y in range(y1+1, y2):
                            ci = max(ci, E[x][y])
                            cnt += E[x][y]
                    if ci < co:
                        ans = max(ans, (x2-x1-1)*(y2-y1-1)*co - cnt)
    print(ans)

Measured memory_bytes: 7704
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (long long i = j; i < (long long)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
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; }
//name[i][j]-> vvl name(i,vl(j))
//map<int,int>mp
//�]���؂�グ�� =>  (a + b - 1) / b 

signed main(){
	int a,b,c; cin>>a>>b>>c;
  cout<<c<<" "<<a<<" "<<b;
  
	
	return 0;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
#define ld double
#define ll long long
#define pb emplace_back
#define mk make_pair
#define mod 1000000007
#define ff first
#define ss second
#define sz(x) (int)x.size()
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(x) x.begin(),x.end()
ll power(ll a, ll b) {ll res = 1; a = a % mod; while (b) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b /= 2;} return res;}
ll invmod(ll a) {return power(a, mod - 2);}
int main(void)
{
	FIO
	int t = 1;
	// cin >> t;
	while (t--)
	{
		ll n, d, x, y, cnt = 0;
		cin >> n >> d;
		d *= d;
		for (int i = 0; i < n; i++) {
			cin >> x >> y;
			x *= x;
			y *= y;
			if (x + y <= d) cnt++;
		}
		cout << cnt;
	}
	return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <utility>
#include <functional>
#include <bitset>
#include <cstdint>

using namespace std;
using lli = long long int;
using i64 = int64_t;
using i32 = int32_t;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (size_t i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (size_t i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

i64 n, m;
i32 g[701][701];

i32 cl[701];

pair<i64, i64> dfs_cl(i64 u, i32 c) {
  cl[u] = c;
  i64 r = c == 1 ? 1 : 0, b = 1 - r;
  for (i64 v = 1; v <= n; ++v) {
    if (u != v && g[u][v] == 0) {
      if (cl[v] == 0) {
        auto p = dfs_cl(v, -c);
        if (p.first == -1) return p;
        r += p.first;
        b += p.second;
      } else if (cl[v] == c) {
        return { -1, -1 };
      }
    }
  }
  return { r, b };
}

int main() {
  cin >> n >> m;
  for (i64 i = 0; i < m; ++i) {
    i64 a, b; cin >> a >> b;
    g[a][b] = g[b][a] = 1;
  }

  vector<pair<i64, i64>> ps;
  for (i64 u = 1; u <= n; ++u) {
    if (cl[u] == 0) {
      ps.push_back(dfs_cl(u, 1));
      if (ps.back().first == -1) { cout << -1 << '\n'; return 0; }
    }
  }

  sort(begin(ps), end(ps));
  vector<bool> f1(800), f2(800);
  f1[0] = true;
  for (auto& p : ps) {
    i64 r = p.first, b = p.second;
    cerr << r << '\t' << b << endl;
    for (i64 x = 750; x > 0; --x) {
      if (x - r >= 0 && f1[x - r]) f2[x] = true;
      if (x - b >= 0 && f1[x - b]) f2[x] = true;
    }
    swap(f1, f2);
    fill(begin(f2), end(f2), false);
  }

  i64 ans = 1ll << 50;
  for (i64 x = 0; x <= 750; ++x) {
    if (f1[x]) {
      i64 y = n * (n - 1) / 2 - x * (n - x);
      ans = min(ans, y);
    }
  }

  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 2176
/*
      author : Nishikawa
      created: 06.08.2020 22:22:11
*/

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


int main(){
    int x;
    int n;
    cin >> x >> n;
    vector<int> p(n+1);
    vector<int> q(201,1);
    for(int i=1; i<=n; i++) cin >> p[i];
    for(int i=1; i<=n; i++) q[p[i]]=0;

    int cnt=1;
    int y = x;
    while(1){
        if(cnt&1){
            if(q[x]!=0 || x<0){
                cout << x << endl;
                return 0;
            }
            x--;
        }
        else{
            if(q[y]){
                cout << y << endl;
                return 0;
            }
            y++;
        }
        cnt++;
    }
    cout << x << endl;
    return 0;
}

Measured memory_bytes: 3624
<?php

list($h, $w) = preg_split('/ /', trim(fgets(STDIN)));

$map = [];
$dp = [];
for ($i = 0; $i < $h; $i++) { 
    $map[$i] =  preg_split('//', trim(fgets(STDIN)), -1, PREG_SPLIT_NO_EMPTY);
}

print (ceil(score($h - 1, $w - 1) / 2));

function score($r, $c) {
    global $h, $w, $map, $dp;
    if (isset($dp[$r][$c])) return $dp[$r][$c];

    if ($r == 0 && $c == 0) return ($map[$r][$c] == "#") ? 1 : 0;

    $s1 = $s2 = PHP_INT_MAX;
    if ($r != 0) {
        $s1 = score($r-1, $c);
        if ($map[$r-1][$c] != $map[$r][$c]) $s1++;
    }
    
    if ($c != 0) {
        $s2 = score($r, $c-1);
        if ($map[$r][$c-1] != $map[$r][$c]) $s2++;
    }

    return $dp[$r][$c] = min($s1, $s2);
}

Measured memory_bytes: 9192
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int a, b,ans =0;
	
	cin>> a>>b;
	if(a<=5){
		ans = 0;
	}else if(6<=a&&a<=12){
		ans = b/2;
	}else{
		ans = b;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 3584
#include<cstdio>
#include<algorithm>
#define N_ 101000
using namespace std;
int n, K, w[N_];
int main() {
	int i, pv = 0;
	scanf("%d%d", &n, &K);
	printf("%d\n", (n-1+K-2)/(K-1));
}

Measured memory_bytes: 128
a, b = map(int, input().split())
from fractions import gcd
from numpy import sqrt
m = gcd(a,b)
cnt = 1
for i in range(2, int(sqrt(m))+1):
    div = False
    while m%i == 0:
        div = True
        m = m//i
    if div:
        cnt += 1
    if m == 1:
        break
if m > 1:
    cnt += 1
print(cnt)

Measured memory_bytes: 13632
#include <bits/stdc++.h>
using namespace std;
#define popcnt(a) __builtin_popcount(a)
#define FastIO() ios::sync_with_stdio(false), cin.tie(0);
#define IO() freopen("palindrome.in","rw",stdin)
#define error(args...)                       \
{                                            \
    cerr<<"LINE "<<__LINE__;                 \
    string _s = #args;                       \
    replace(_s.begin(), _s.end(), ',', ' '); \
    stringstream _ss(_s);                    \
    istream_iterator<string> _it(_ss);       \
    err(_it, args);                          \
    cerr<<endl;                              \
}
void err(istream_iterator<string> it)
{
} 
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args)
{
  cerr<<' '<< *it << " = " << a ;
  err(++it, args...);
} 
typedef long long ll;
const int N = 1e6+9, M = 1e2+9, OO = 0x3f3f3f3f,MOD = 1e9 + 7;
int par[N],sz[N],arr[N],n;
void init()
{
  iota(par+1,par+n+1,1);
  fill(sz,sz+n+1,1);
}
int find(int p)
{
  return p==par[p] ? p : par[p]=find(par[p]);
}
void join(int a,int b)
{
  a = find(a);
  b = find(b);
  if(a==b) return;
  if(sz[a]<sz[b]) swap(a,b);
  par[b] =a;
  sz[a] += sz[b];

}
int main()
{
  
  int m,ans=0;
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;++i) scanf("%d",arr+i);
  init();
  while(m--)
  {
    int x,y;
    scanf("%d%d",&x,&y);
    join(par[x],par[y]);
  }
  for(int i=1;i<=n;++i) ans += (find(i)==find(arr[i]));
  
  printf("%d\n",ans);
  #ifdef _LOCAL_DEFINE  
  cerr << (double)clock() * 1.0 / CLOCKS_PER_SEC << endl;
  #endif
  return 0; 
}



Measured memory_bytes: 8832
#include <iostream>

using namespace std;

int solve(int y, int m, int d) {
  int ret = 0;
  for (int i = y; i < 1000; i++) {
    for (int j = m; j < 11; j++) {
      int D = 0;
      if (i % 3 != 0 && j % 2 == 0) {
        D = 19;
      } else {
        D = 20;
      }
      ret += D - d + 1;
      d = 1;
    }
    m = 1;
  }

  return ret;
}

int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    int y, m, d;
    cin >> y >> m >> d;
    cout << solve(y, m, d) << endl;
  }
  
  return 0;
}

Measured memory_bytes: 1160
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
    
		// 文字列の入力
		ArrayList<String> list = new ArrayList<>();
        for(int i = 0; i < 4; i++) {
          list.add(sc.next());
        }
    
		// 出力
		System.out.println(list.contains("1") 
                           && list.contains("9")
                           && list.contains("7")
                           && list.contains("4") ? "YES" : "NO");
	}
}

Measured memory_bytes: 21844
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right
from heapq import heappush, heappop

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
import sys
sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e30)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    S = input()
    T = input()
    ans = 0
    for s, t in zip(S, T):
        if s == t:
            ans += 1
    print(ans)
if __name__ == "__main__":
    main()


Measured memory_bytes: 38384
import java.util.Scanner;
class Main{
    public static void main(String[] av){
	Scanner sc=new Scanner(System.in);
        	int i=1;
	while(true){
	  int  x=sc.nextInt();
	  int y=sc.nextInt();
	    if(x==0&&y==0) break;
	    else{
		if(x>y){
		    System.out.println(y+" "+x);
		}else{
		    System.out.println(x+" "+y);
		}
	    }
	}

    
    
    }
}


Measured memory_bytes: 36232
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)
 
#define DEBUG(x) cout<<#x<<": "<<x<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n'
#define ALL(a) (a).begin(), (a).end()
 
#define CHMIN(a, b) a=min((a), (b))
#define CHMAX(a, b) a=max((a), (b))
 
const ll MOD=1000000007ll;
// const ll MOD=998244353ll;
#define FIX(a) ((a)%MOD+MOD)%MOD
 
const double EPS=1e-11;
#define EQ0(x) (abs((x))<EPS)
#define EQ(a, b) (abs((a)-(b))<EPS)
 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, a[114514];
	cin>>n;
	REP(i, n){
		cin>>a[i];
	}
	if(n==1){
		cout<<1<<'\n';
		return 0;
	}
	int f=0, ans=1;
	REP(i, n-1){
		if(f==0){
			if(a[i]<a[i+1]){
				++f;
			}
			else if(a[i]>a[i+1]){
				--f;
			}
		}
		if(f==1){
			if(a[i]>a[i+1]){
				++ans;
				--f;
			}
		}
		else{
			if(a[i]<a[i+1]){
				++ans;
				++f;
			}
		}
	}
	cout<<ans<<'\n';
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#ifdef ENABLE_DEBUG
#define dump(a) cerr<<#a<<"="<<a<<endl
#define dumparr(a,n) cerr<<#a<<"["<<n<<"]="<<a[n]<<endl
#else
#define dump(a) 
#define dumparr(a,n) 
#endif
#define FOR(i, a, b) for(ll i = a;i < b;i++)
#define For(i, a) FOR(i, 0, a)
#define REV(i, a, b) for(ll i = b-1;i >= a;i--)
#define Rev(i, a) REV(i, 0, a)
#define REP(a) For(i, a)
#define SIGN(a) (a==0?0:(a>0?1:-1))

typedef long long int ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<ll, ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;
typedef long double ld;
typedef pair<ld,ld> pdd;

const ll INF=(1LL<<50);
#if __cplusplus<201700L
ll gcd(ll a, ll b) {
  if(a < b) return gcd(b, a);
  ll r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}
#endif

template<class S,class T>
std::ostream& operator<<(std::ostream& os,pair<S,T> a){
  os << "(" << a.first << "," << a.second << ")";
  return os;
}
template<class T>
std::ostream& operator<<(std::ostream& os,vector<T> a){
  os << "[ ";
  REP(a.size()){
    os<< a[i] << " ";
  }
  os<< " ]";
  return os;
}

pll pllminmax(ll i,ll j){
  return pll(min(i,j),max(i,j));
}

void solve(long long N, long long M, std::vector<long long> D, std::vector<long long> U, std::vector<long long> V){
  vector<vector<ll>> mp(N);
  map<pll,ll> weight;
  set<pll> edges;
  vector<char> bw(N,0);
  REP(M){
    mp[U[i]].push_back(V[i]);
    mp[V[i]].push_back(U[i]);
    edges.insert(pllminmax(U[i],V[i]));
  }
  vector<pll> d(N);
  REP(N){
    d[i]=pll(D[i],i);
  }
  sort(d.begin(),d.end());
  ll i=0;
  while(i<N){
    ll cur=d[i].second;
    ++i;
    if(bw[cur]!=0)continue;
    bool f=false;
    for (auto &&j : mp[cur])
    {
      if(D[cur]>=D[j]){
        if(bw[j]==0){
          bw[j]='W';
          bw[cur]='B';
        }else{
          bw[cur]=(bw[j]=='W'?'B':'W');
        }
        weight[pllminmax(cur,j)]=D[cur];
        f=true;
        break;
      }
    }
    if(f){
      continue;
    }else{
      cout<<-1<<endl;
      return;
    }
  }
  cout<<string(bw.begin(),bw.end())<<endl;
  REP(M){
    if(weight.count(pllminmax(U[i],V[i]))){
      cout<<weight[pllminmax(U[i],V[i])]<<endl;
    }else{
      cout<<1000000000<<endl;
    }
  }
}

int main(){
  cout<<setprecision(1000);
  cin.tie(0);
  ios::sync_with_stdio(false);
    long long N;
    scanf("%lld",&N);
    long long M;
    scanf("%lld",&M);
    std::vector<long long> D(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&D[i]);
    }
    std::vector<long long> U(M);
    std::vector<long long> V(M);
    for(int i = 0 ; i < M ; i++){
        scanf("%lld",&U[i]);
        scanf("%lld",&V[i]);
        --U[i];
        --V[i];
    }
    solve(N, M, std::move(D), std::move(U), std::move(V));
    return 0;
}


Measured memory_bytes: 34688
#毎回関数を呼ぶとおそくなる
n = int(input())
stones = input()
score = stones.count(".")
r = score
for i in range(n):
	if stones[i] == ".":
		r -= 1
	else:
		r += 1
	score = min(r, score)
print(score)	

Measured memory_bytes: 3500
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(I,A,B) for(ll I = (A); I < (B); ++I)
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //ai>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //ai>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define REV(x) (reverse(x.begin(),x.end())) //reverse
#define TO(x,t,f) ((x)?(t):(f))
#define CLR(mat) memset(mat, 0, sizeof(mat))
#define FILV(x,a) fill(x.begin(),x.end(),a)
#define FILA(ar,N,a) fill(ar,ar+N,a)
#define NEXTP(x) next_permutation(x.begin(),x.end())
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;else return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
#define pb push_back
#define pri(aa) cout<<(aa)<<endl
const ll INF=1e9+7;
const ll N = 200002;
multiset<string> a,b;
vector<string> v;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    FOR(i,0,n){
    	string s;
    	cin>>s;
    	v.pb(s);
    	a.insert(s);
    }
    cin>>n;
    FOR(i,0,n){
    	string s;
    	cin>>s;
    	b.insert(s);
    }
    int ans=0;
    FOR(i,0,v.size()){
    	ans=max(ans,(int)a.count(v[i])-(int)b.count(v[i]));
    }pri(ans);
    return 0;
}


Measured memory_bytes: 256
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<list>
#include<bitset>
#include<stack>
#include<memory>
#include<numeric>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);*/
const int mod=998244353 ;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-10;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(const vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(const vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
int main(void){
	llint i,j,n,m;cin>>n>>m;
	vector<vector<pair<int,llint>>>go(n);
	for(i=0;i<m;i++){
		int L,R;llint C;cin>>L>>R>>C;
		L--;R--;
		go[L].pub(mp(R,C));
	}
	set<pair<int,llint>>dp;
	dp.ins(mp(0,0LL));
	dp.ins(mp(n+1,big));
	for(i=0;i<n-1;i++){
		if(dp.begin()->fir >n){cout<<-1<<endl;return 0;}
		llint now=dp.begin()->sec;
		while(dp.begin()->fir <=i){dp.erase(dp.begin());}
		for(auto it:go[i]){
			llint cost=now+it.sec;
			int ter=it.fir;
			auto itr=dp.lower_bound(mp(ter,cost));
			if(cost >= itr->sec){continue;}
			itr=dp.insert(itr,mp(ter,cost));
			while(itr!=dp.begin()&&prev(itr)->sec >= cost){dp.erase(prev(itr));}
		}
		
		//for(auto it:dp){cerr<<it.fir<<" "<<it.sec<<endl;}
		//cerr<<"debag"<<endl;
	}
	if(dp.begin()->fir!=n-1){cout<<-1<<endl;}
	else{cout<<dp.begin()->sec<<endl;}
	return 0;
}


Measured memory_bytes: 5632
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] nums = br.readLine().trim().split(" ");
		BigInteger n = new BigInteger(nums[0]);
		BigInteger m = new BigInteger(nums[1]);
		BigInteger mod = new BigInteger("1000000007");

		System.out.println(n.modPow(m, mod));

		if (br != null) {
			br.close();
			br = null;
		}
	}
}

Measured memory_bytes: 17096
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(x),end(x)
#define show(obj) {for(auto x:obj)cout<<x<<' ';cout<<endl;}
#define line "----------"
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> LP;
const int inf = 1001001000;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

ll rep_power_modM(ll a, ll n, ll M = MOD){
	if(n == 0)return 1;
	if(n%2 == 0){ll tmp = rep_power_modM(a,n/2,M); return tmp*tmp%M;}
	return a*rep_power_modM(a,n-1,M)%M;
}

int main(){
	string s;
	cin >> s;
	int N = s.size();
	vector<vector<ll>> dp(N+1, vector<ll>(13, 0));
	dp[0][0] = 1;
	rep(i,N)rep(j,13){
		ll ni = i + 1, nj = rep_power_modM(10, N-1-i, 13);
		if(s[i] == '?'){
			rep(nd,10){
				ll rnj = (nj*nd + j) % 13; 
				dp[ni][rnj] += dp[i][j];
				dp[ni][rnj] %= MOD;
			}
		}else{
			ll rnj = (nj*(s[i]-'0') + j) % 13;
			dp[ni][rnj] += dp[i][j];
			dp[ni][rnj] %= MOD;
		}
	}
	//REP(i,N){rep(j,13)cout << dp[i][j]<< ' ';cout << endl;}
	cout << dp[N][5] << endl;
	return 0;
}


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

#define inf 9999999

int min(int a,int b)
{
  if(a<b)
    return a;
  else
    return b;
}

int main(void)
{
  int i,j,m,n,*T,*c;
  scanf("%d %d",&n,&m);
  T=malloc(sizeof(int)*(n+1));
  c=malloc(sizeof(int)*(m));

  for(i=0;i<m;i++)
    scanf("%d",&c[i]);
  T[0]=0;
  for(i=1;i<n+1;i++)
    T[i]=inf;

  for(i=0;i<m+1;i++)
    for(j=c[i];j<n+1;j++)
      T[j]=min(T[j],T[j-c[i]]+1);
  
  printf("%d\n",T[n]);
  return 0;
}

Measured memory_bytes: 792
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<deque>
#include<queue>
#include<stack>
using namespace std;
#define int long long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
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; }
typedef pair<int, int>P;
const int MOD = 1e9 + 7;
//const int MOD = 998244353;
const int INF = 1e18;
const long double PI = (acos(-1));


struct UnionFind {
	vector<int> d; // d[i]:iの親の番号　(例) d[3] = 2 : 3の親が2 d[3] = -3 : 3は根で、その連結成分のサイズは3

	UnionFind(int N) : d(N, -1) {} // 負なら根である 非負なら子である

	int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
		if (d[x] < 0) return x; //負なら根であるから根を返す
		return d[x] = root(d[x]);
	}

	bool unite(int x, int y) { // xとyの木を併合
		int rx = root(x); //xの根をrx
		int ry = root(y); //yの根をry
		if (rx == ry) return false; //xとyの根が同じ(=同じ木にある)時はそのまま
		if (d[rx] > d[ry])swap(rx, ry); //木のサイズが大きいほうにくっつける
		d[rx] += d[ry]; //サイズが上乗せされる
		d[ry] = rx; //yの根はxになる
		return true;
	}

	bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
	int size(int x) {
		return -d[root(x)];
	}
};

signed main() {
	int N, M;
	cin >> N >> M;
	vector<int>a(M), b(M);
	rep(i, M)cin >> a[i] >> b[i];
	rep(i, M)a[i]--;
	rep(i, M)b[i]--;
	int ans = 0;
	rep(i, M) {
		UnionFind tree(N);
		rep(j, M) {
			if (j == i)continue;
			tree.unite(a[j], b[j]);
		}
		if (tree.size(0) != N)ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
<>;
chomp(my $s = <>);
my ($max_l, $min_r) = split(/\s/, $s);
while (<>) {
    chomp;
    my ($L, $R) = split(/\s/);
    $max_l = $L if $L > $max_l;
    $min_r = $R if $R < $min_r;
}
my $x = $min_r - $max_l;
print($x >= 0 ? $x + 1 : 0, "\n");


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

int main(){
  int N,D,result=0;
  double tmp;
  cin >> N >> D;
  int X[N][D];

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

  for(int i=0;i<N-1;i++){
    for(int j=i+1;j<N;j++){
      for(int l=0;l<D;l++){
        tmp += (X[i][l]-X[j][l])*(X[i][l]-X[j][l]);
      }
      tmp = sqrt(tmp);
      if(ceil(tmp) == floor(tmp)){
        result += 1;
      }
      tmp = 0;
    }
  }

  cout << result << endl;
}


Measured memory_bytes: 256
import sys
import copy
import math
import bisect
import pprint
import bisect
from functools import reduce
from copy import deepcopy
from collections import deque

if __name__ == '__main__':
    a = int(input())
    b = int(input())
    c = int(input())
    ans = a -b
    ans = ans %c
    print(ans)

Measured memory_bytes: 3828
#include<stdio.h>

int main(){
    int n, q;
    long int sum=0, count[1000000]={0}, p;
    scanf("%d", &n);
    for(int i=0; i<n; i++){
        scanf("%ld", &p);
        count[p]++;
        sum = sum + p;
    }
    scanf("%d", &q);
    int b[1000000], c[1000000];
    for(int i=0; i<q; i++){
        scanf("%d%d", &b[i], &c[i]);
        sum = sum + (c[i]-b[i])*count[b[i]];
        printf("%ld\n", sum);
        count[c[i]] = count[c[i]] + count[b[i]];
        count[b[i]] = 0;
    }
}





Measured memory_bytes: 10336
import java.io.*;
import java.util.*;


public class Main {

    public static void main(String[] args) {
        FastScanner sc = new FastScanner(System.in);
        System.out.println(getDigit(sc.nextInt(), sc.nextInt()));
    }

    static int getDigit(int n, int d) {
        return n / d != 0 ? 1 + getDigit(n / d, d) : 1;
    }

    static class FastScanner {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        public FastScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
            tokenizer = null;
        }

        public String next() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public String nextLine() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    return reader.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return tokenizer.nextToken("\n");
        }

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

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

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


        public long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }
    }
}

Measured memory_bytes: 22612
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
using namespace std;
#define rep(i,n) for(int i = 0;i<n;i++)
const long long MOD = 1000000007LL;
const string alpha = "abcdefghijklmnopqrstuvwxyz";
bool judge(long num[],long n){
    rep(i,n){
        if(num[i+1]%2==1) return false;
    }
    return true;
}
int main(){
    long n,m;
    cin >> n >> m;
    long num[n+1];
    rep(i,n){
        num[i+1]=0;
    }
    long a,b;
    rep(i,m){
        cin >> a >> b;
        num[a]++;
        num[b]++;
    }
    if(judge(num,n)) cout << "YES" << endl;
    else cout << "NO" << endl;
}

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

int main(){

int r,c;
cin>>r>>c;

int table[r+1][c+1]={};

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

for(int i=0;i<r+1;i++){
    for(int j=0;j<c+1;j++){
        if(j==c){
            cout<<table[i][j]<<endl;
        }else{
            cout<<table[i][j]<<" ";
        }
    }
}



    return 0;
}


Measured memory_bytes: 3120