akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
#define INF 1<<25
using namespace std;
string s[101];
typedef pair<int,int> P;
int w,h,a[101][101],sx,sy,gx,gy;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int dx1[]={1,1,1,0,0,-1,-1,-1};
int dy1[]={1,0,-1,1,-1,1,0,-1};
int dx2[]={2,2,2,2,2,1,1,0,0,-1,-1,-2,-2,-2,-2,-2};
int dy2[]={2,1,0,-1,-2,2,-2,2,-2,2,-2,2,1,0,-1,-2};
vector<P>G[10001];
vector<int>maki;
void make_map(int y,int x){
  a[y][x]=INF;
  r(i,8){
    int xx=x+dx1[i];
    int yy=y+dy1[i];
    if(xx<0||yy<0||yy>=h||xx>=w)continue;
    if(a[yy][xx]<3)a[yy][xx]=3;
  }
  r(i,16){
    int xx=x+dx2[i];
    int yy=y+dy2[i];
    if(xx<0||yy<0||yy>=h||xx>=w)continue;
    if(a[yy][xx]<2)a[yy][xx]=2;
  }
}
int d[10001];
void dijkstra(int s){
  priority_queue<P,vector<P>,greater<P> >que;
  fill(d,d+10001,INF);
  d[s]=0;
  que.push(P(0,s));
  while(!que.empty()){
    P p=que.top();que.pop();
    int v=p.second;
    if(d[v]<p.first)continue;
    for(int i=0;i<G[v].size();i++){
      P e=G[v][i];
      if(d[e.first]>d[v]+e.second){
        d[e.first]=d[v]+e.second;
        que.push(P(d[e.first],e.first));
      }
    }
  }
}
int ans=INF,used[101]={},koko;
int dis[101][101];
void dfs(int depth,int dista,int cur){
  if(depth==koko-1){
    //cout<<dista<<endl;
    ans=min(ans,dista);
    return;
  }
  if(depth<koko-2){
    for(int i=1;i<koko-1;i++)
      if(!used[i]){
      used[i]=1;
      dfs(depth+1,dista+dis[cur][i],i);
      used[i]=0;
    }
  }
  else{
    used[cur]=1;
    dfs(depth+1,dista+dis[cur][koko-1],cur);
    used[cur]=0;
  }
}
main(){
  r(i,101)r(j,101)a[i][j]=1;
  cin>>w>>h;
  r(i,h)cin>>s[i];
  r(i,h)r(j,w){
    if(s[i][j]=='#')make_map(i,j);
    if(s[i][j]=='S')sx=i*w+j;
    if(s[i][j]=='G')gx=i*w+j;
    if(s[i][j]=='M')maki.push_back(i*w+j);
  }
  r(i,h)r(j,w)r(k,4){
    int xx=j+dx[k];
    int yy=i+dy[k];
    if(xx<0||yy<0||yy>=h||xx>=w)continue;
    if(k==0)G[i*w+j].push_back(P(i*w+j+1,a[i][j]));
    if(k==1)G[i*w+j].push_back(P(i*w+j-1,a[i][j]));
    if(k==2)G[i*w+j].push_back(P(i*w+w+j,a[i][j]));
    if(k==3)G[i*w+j].push_back(P(i*w-w+j,a[i][j]));
  }
  int num=maki.size()+2;
  vector<int>ps;
  ps.push_back(sx);
  r(i,maki.size())ps.push_back(maki[i]);
  ps.push_back(gx);
  r(i,num){
    dijkstra(ps[i]);
    r(j,num)dis[i][j]=d[ps[j]];
  }
  koko=num;
  used[0]=1;
  dfs(0,0,0);
  cout<<ans<<endl;
}

Measured memory_bytes: 3944
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <utility>
#include <ctime>
#define INF 100000000
#define LINF 9000000000000000000
#define mod 1000000007
 
#define rep(i,n) for(int i=0;i<int(n);i++)
#define rrep(i,n) for(int i=(n);i>=0;i--)
#define REP(i,a,b) for(int i=(a);i<int(b);i++)
#define all(x) (x).begin(),x.end()
#define vector_rsort(x) sort(all(x));reverse(all(x))
#define array_rsort(x,n) sort(x,x+n);reverse(x,x+n);
#define pb push_back
#define mp make_pair
#define MOD(x) (x%(mod))

#define yes cout<<"yes"<<endl
#define Yes cout<<"Yes"<<endl
#define YES cout<<"YES"<<endl
#define no cout<<"no"<<endl;
#define No cout<<"No"<<endl
#define NO cout<<"NO"<<endl
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pi;
 
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
bool debug=false;
/*---------------------------------------------------*/

int n,m;
int a[1005],b[1005],c[1005];
ll d[105][105];

void init(){
  rep(i,105){
    rep(j,105){
      if(i!=j)d[i][j]=INF;
    }
  }
}

void wf(){
  rep(k,105){
    rep(i,105){
      rep(j,105){
	d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
      }
    }
  }
}

int main(){
  init();
  cin>>n>>m;
  rep(i,m){
    cin>>a[i]>>b[i]>>c[i];
    a[i]--;
    b[i]--;
    d[a[i]][b[i]]=c[i];
    d[b[i]][a[i]]=c[i];
  }
  wf();
  int ans=m;
  rep(i,m){
    bool ok=false;
    rep(j,n){
      if(d[j][a[i]]+c[i]==d[j][b[i]])ok=true;
    }
    if(ok)ans=ans-1;;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <cstring>
#include <string.h>
#include <sstream>
#include <iomanip>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <tuple>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
 
typedef unsigned long ul;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MOD = 1e9+7;
const ll CFMOD = 998244353;
const double PI  = 3.14159265358;
const double EPS = 1e-8;
 
#define INT_MX 2147483647
#define INF ((int)1e9)
#define LLINF ((ll)1e18)
#define F first
#define S second
#define MP(x,y) make_pair(x,y)
#define sz(v) ((int)v.size())
#define rs(n) resize(n)
#define ALL(v) v.begin(),v.end()
#define reset(v) memset((v),0,sizeof(v))
#define EB emplace_back
#define PB push_back
#define PF push_front
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define REP(i,n,m) for(int i=(n);i<(m);i++)
#define vec vector
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);


ll dp[110][100010];

void solve(){
    int n, mxw;
    vec<int> w,v;
    
    cin >> n >> mxw;
    w.rs(n);
    v.rs(n);
    
    rep(i,n) cin >> w[i] >> v[i];
    
    rep1(i,n) rep1(j,mxw){
        dp[i][j] = dp[i-1][j];
        if(j >= w[i-1])    dp[i][j] = max(dp[i][j], dp[i-1][j-w[i-1]] + v[i-1]);
    }
    
    cout << dp[n][mxw] << '\n';
    
}
 
int main(){
    int t = 1;
    
    while(t--){
        solve();
    }
}


Measured memory_bytes: 79488
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main {

  public static void main(String[] args) {

    Map<String, String> base = new HashMap<>();
    base.put("A","T");
    base.put("T","A");
    base.put("C","G");
    base.put("G","C");

    String in = null;
    try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))){
      in = br.readLine();
    } catch (IOException e) {
      e.printStackTrace();
      System.exit(1);
    }

    System.out.print(base.get(in));

  }
}


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

typedef long long ll;
const ll INF = 1010000000000000017LL;
const ll MOD = 1000000007LL;

#define REP(i, n) for(ll i = 0 ; i < n; i++)

//#define DEBUG(fmt, ...)
#define DEBUG(fmt, ...) fprintf(stderr, fmt "\n", ##__VA_ARGS__)

ll gcd(ll a, ll b)
{
   for (;;)
   {
      if (a == 0) return b;
      b %= a;
      if (b == 0) return a;
      a %= b;
   }
}

ll lcm(ll a, ll b)
{
   ll temp = gcd(a, b);

   return temp ? (a / temp * b) : 0;
}

int main(){
    std::cout<<std::fixed<<std::setprecision(10);

    ll A, B, C, D;
    cin >> A >> B >> C >> D;

    ll CD = C*D;

    ll countB = B/C;
    ll countA = (A-1)/C;

    ll c = countB-countA;

    countB = B/D;
    countA = (A-1)/D;

    ll d = countB-countA;

    countB = B/lcm(C,D);
    countA = (A-1)/lcm(C,D);

    ll cd = countB-countA;

    cout << ((B-A+1) - (c+d-cd)) << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i,n) for(long long i = 0; i < (n); ++i)
#define ll long long
#define P pair<ll,ll>
#define all(v) (v).begin(),(v).end()

const ll mod = 1e9+7;
const ll INF = 1e18;
const double pi = acos(-1.0);

int main(void)
{
    ll n; cin>>n;
    vector<ll> a(n);
    rep(i,n) cin>>a[i];

    ll maxi=a[0],sum=0;
    for(int i=1;i<n;i++){
        if(a[i] > maxi){
            maxi = a[i];
        }else{
            sum += abs(a[i]-maxi);
        }
    }
    cout<<sum<<endl;
    return 0;
}

Measured memory_bytes: 4836
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> Pll;
typedef pair<P,P> PP;
#define rep(i,a,n) for(int i = a;i < n;i++)
#define LINF (ll)1e17
#define INF 1e9
#define MOD 1e9+7
#define sMOD 1e5
#define fs first
#define sc second

ll gcd(ll a,ll b){
	if(!b) return a;
	return gcd(b,a%b);
}

signed main(){
	ll a,b,c;
	
	cin >> a >> b >> c;
	
	if(a == b && b == c) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;

}


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

int main(){
	string s;
	cin >> s;
	bool ok = true;
	int k = 0;
	for(int k=0; k<s.size(); k++){
		if(k%2 == 0) if(s[k]!='R' && s[k]!='U' && s[k]!='D') ok = false;
		if(k%2 != 0) if(s[k]!='L' && s[k]!='U' && s[k]!='D') ok = false;
    }
	ok ? puts("Yes") : puts("No");
	return 0;
}

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

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = std::int64_t;
using P = std::tuple<int,int>;

std::string S, T;
int memS, memT;
std::vector<int> v[26];

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

  std::cin >> S >> T;

  int N = S.size(), M = T.size();

  for(int i=0;i<N;++i){
      char c = S[i];
      memS = memS | (1 << (c - 'a'));
      v[c - 'a'].emplace_back(i);
  }

  for(int i=0;i<M;++i){
      char c = T[i];
      memT = memT | (1 << (c - 'a'));
  }

  for(int i=0;i<26;++i){
      unless(!(memT >> i & 1) || (memS >> i & 1)){
          std::cout << "-1" << std::endl;
          return 0;
      }
  }

  ll pos = -1, res = 0;

  for(int i=0;i<M;++i){
      char c = T[i];
      int j = c - 'a';
      int nxt = std::upper_bound(v[j].begin(), v[j].end(), pos) - v[j].begin();

      if(nxt < v[j].size()){
          nxt = v[j][nxt];
          res += nxt - pos;
          pos = nxt;
      }else{
          nxt = v[j][0];
          res += nxt + N - pos;
          pos = nxt;
      }
  }

  std::cout << res << std::endl;
}


Measured memory_bytes: 1228
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;
 
import java.util.*;
import java.lang.*;
import java.io.*;

@SuppressWarnings("unchecked")
public class Main implements Runnable {

  static BufferedReader in;
  static PrintWriter out;

  static int minInversionsNeeded;
  static boolean[][] isOpenCell;
  static int[][] ways;
 
  public static void main(String[] args) {
      new Thread(null, new Main(), "whatever", 1<<29).start();
  }

  public void computeWays(int i, int j) {
    if(i-1>=0) {
      int newInversionsNeeded=ways[i-1][j];
      if(isOpenCell[i-1][j] && !isOpenCell[i][j]) {
        newInversionsNeeded++;
      }
      ways[i][j]=Math.min(ways[i][j], newInversionsNeeded);
    }
    if(j-1>=0) {
      int newInversionsNeeded=ways[i][j-1];
      if(isOpenCell[i][j-1] && !isOpenCell[i][j]) {
        newInversionsNeeded++;
      }
      ways[i][j]=Math.min(ways[i][j], newInversionsNeeded);
    }
  }
 
  public void run() {
    in = new BufferedReader(new InputStreamReader(System.in));
    out = new PrintWriter(System.out, false);
 
    try
    {
      // in = new BufferedReader(new FileReader("class_treasurer.txt"));
      // out = new PrintWriter("output.txt");

      int t,x1,n,m,i,j;
      String str;
      String[] token;

      str=in.readLine().trim();
      token=str.split(" ");

      n=Integer.parseInt(token[0]);
      m=Integer.parseInt(token[1]);

      isOpenCell = new boolean[n][m];
      ways = new int[n][m];

      for(i=0;i<n;i++) {
        str=in.readLine().trim();
        for(j=0;j<m;j++) {
          if(str.charAt(j)=='#') {
            isOpenCell[i][j]=false;
          }
          else {
            isOpenCell[i][j]=true;
          }
          ways[i][j]=n*m;
        }
      }

      minInversionsNeeded=n*m;

      int inversionsNeeded=0;
      if(!isOpenCell[0][0]) {
        inversionsNeeded++;
      }

      ways[0][0]=inversionsNeeded;

      for(i=0;i<n;i++) {
        for(j=0;j<m;j++) {
          computeWays(i, j);
        }
      }

      out.println(ways[n-1][m-1]);

      out.flush();
      out.close();
    }
    catch(Exception e) {
      e.printStackTrace();
    }
  }
}


Measured memory_bytes: 23636
#include <bits/stdc++.h>
using namespace std;
int main(){
    int N;
    cin>>N;
    int sum=0;
    vector<int>p(20);
    for (int i=0;i<N;++i){
        cin>>p[i];
    }
    
    for(int i=1;i<N-1;++i){
            if(p[i-1]<p[i]&&p[i]<p[i+1]){
                    sum++;
            }
            else if(p[i-1]>p[i]&&p[i]>p[i+1]){
                    sum++;
    }
    }
    cout<<sum<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF (INT_MAX / 4)
#define REP(i, n) for (ll i = 0, i##_len = (n); i < i##_len; ++i)
#define ALL(a) (a).begin(), (a).end()
/* clang-format off */
#define TIMER_S(start) chrono::system_clock::time_point start = chrono::system_clock::now();
#define TIMER_E(end) chrono::system_clock::time_point end = chrono::system_clock::now();
#define TIME(start, end) cout << static_cast<double>(chrono::duration_cast<chrono::microseconds>(end - start).count()) << "ms" << "\n";
/* clang-format on */

int main() {
  string s;
  cin >> s;
  int n = s.at(s.size() - 1)-'0';
  if (n == 3)
    cout << "bon"
         << "\n";
  else if (n == 1 || n == 0 || n == 6 || n == 8)
    cout << "pon"
         << "\n";
  else
    cout << "hon"
         << "\n";
  return 0;
}


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

int main(){
  //ifstream in("input.txt");
  //cin.rdbuf(in.rdbuf());

  int N,T;
  cin>>N>>T;

  vector<int> t(N);
  for(int i=0;i<N;i++) cin>>t.at(i);

  int ima=0;
  int kako=0;
  int oyu=0;

  for(int i=0;i<N-1;i++){
    ima = ima + T;
    if(ima>t.at(i+1)){
      ima = t.at(i+1);
      oyu += (ima-kako);
    }
    else{
      oyu += T;
      ima = t.at(i+1);
    }
    kako = ima;
  }
  oyu += T;

  cout<<oyu<<endl;

}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <ctime>
#include <vector>
#include <queue>
#include <stack>
#include <map>

using namespace std;

#define rep(i, l, r) for (int i = l; i <= r; i ++)
#define dwn(i, r, l) for (int i = r; i >= l; i --)
#define repG(u, i) for (int i = hd[u]; i; i = e[i].nxt)
#define ev e[i].v
#define ec e[i].c
#define sqr(x) (x)*(x)
#define rlxX(x, y) x = max(x, y)
#define rlxN(x, y) x = min(x, y)
#define clr(a, b) memset(a, b, sizeof(a))
#define gc getchar()

typedef long long LL;
typedef double db;
const int N = 5e5 + 5, INF = 1e9 + 7;

int rd() {
	char ch = gc; int ret = 0;
	while (ch < '0' || ch > '9') ch = gc;
	while (ch >= '0' && ch <= '9') ret = ret*10 + ch-'0', ch = gc;
	return ret;
}

int n, n0[N], n1[N];
char str0[N], str1[N];

void getnext(char str[], int next[]) {
	//cout << str+1 << endl;
	int j = 0; next[1] = 0;
	rep(i, 2, n) {
		while (j && str[j+1] != str[i]) j = next[j];
		if (str[j+1] == str[i]) j ++;
		next[i] = j;
	}
	//cout << n << endl;
	//rep(i, 1, n) printf("%d ", next[i]); puts("");
}

bool can(int x, int y) {return x==y || x%y;}

int main(){
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);

	scanf("%s", str0+1);
	n = strlen(str0+1);
	getnext(str0, n0);
	//cout << n0[n] << endl;

	if (can(n, n-n0[n])) {puts("1\n1"); return 0;}
	if (n-n0[n] == 1) {printf("%d\n1\n", n); return 0;}
	//strcpy(str1+1, str0+1);
	//cout << str1+1 << endl;
	rep(i, 1, n) str1[i] = str0[n-i+1];
	getnext(str1, n1);
	int ans = 0;
	rep(i, 1, n-1) 
		if (can(i, i-n0[i]) && can(n-i, n-i-n1[n-i])) ans ++;
	printf("%d\n%d\n", 2, ans);
	
	return 0;
}
/*

*/



Measured memory_bytes: 5120
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;

int main(void){
int k,x;
  cin >> k >> x;
  if(k*500>=x){
  	cout << "Yes"<<endl;
  }else{
    cout << "No" ;
  }

return 0;
}


Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

count = 0

for num in range(N):
    if A[num] >= B[num]:
        num_dead_monster = B[num]
    else:
        num_dead_monster = A[num]
    #print("now index", num_dead_monster)
    count += num_dead_monster
    A[num] -= num_dead_monster
    B[num] -= num_dead_monster
    
    if B[num] >= 1:
        if A[num+1] >= B[num]:
            num_dead_monster = B[num]
        else:
            num_dead_monster = A[num+1]
        count += num_dead_monster
        A[num+1] -= num_dead_monster
        #print("next index", B[num])
    
    #print("A", A)
    #print("B", B)
    #print()

print(count)

Measured memory_bytes: 19156
use std::io::Read;
use std::cmp;

fn main(){
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).ok();
    let mut it = buf.split_whitespace();
    let h = it.next().unwrap().parse::<usize>().unwrap();
    let w = it.next().unwrap().parse::<usize>().unwrap();
    let s = (0..h).map(|_| it.next().unwrap().as_bytes()).collect::<Vec<_>>();
    let mut dp = vec!(vec!(100000; w); h);
    dp[0][0] = if s[0][0] == '#' as u8 { 1 } else { 0 };
    for i in 0..h {
        for j in 0..w {
            if i+1 < h {
                dp[i+1][j] = cmp::min(dp[i+1][j], dp[i][j] + if s[i][j] == '.' as u8 && s[i+1][j] == '#' as u8 { 1 } else { 0 });
            }
            if j+1 < w {
                dp[i][j+1] = cmp::min(dp[i][j+1], dp[i][j] + if s[i][j] == '.' as u8 && s[i][j+1] == '#' as u8 { 1 } else { 0 });
            }
        }
    }
    println!("{}", dp[h-1][w-1]);
}

Measured memory_bytes: 4352
(defparameter *dx-dy*
  '((-1 . -1)
    (-1 . 0)
    (-1 . 1)
    (0 . -1)
    (0 . 1)
    (1 . -1)
    (1 . 0)
    (1 . 1)))



(defun solve (h w board)
  (declare (optimize speed))
  (labels ((count-mine (y x board &optional (cnt 0))
             (dotimes (d 8 cnt)
               (let ((nx (+ x (first (nth d *dx-dy*))))
                     (ny (+ y (rest (nth d *dx-dy*)))))
                 (when (and (<= 0 nx (1- w))
                            (<= 0 ny (1- h))
                            (char-equal (aref (aref board ny) nx) #\#))
                   (incf cnt))))))
    (dotimes (i h)
      (dotimes (j w)
        (unless (char-equal (aref (aref board i) j) #\#)
          (setf (aref (aref board i) j) (digit-char (count-mine i j board))))))
    board))

(defun main ()
  (declare (optimize speed))
  (let* ((h (read))
         (w (read))
         (board (make-array h :initial-element "")))
    (dotimes (i h)
      (setf (aref board i) (read-line)))
    (let ((ans (solve h w board)))
      (dotimes (i h)
        (fresh-line)
        (princ (aref ans i))))
    (fresh-line)))

(main)


Measured memory_bytes: 24556
#include <iostream>
//#include <iomanip>
#include <string>
//#include <vector>
//#include <algorithm>
//#include <utility>
//#include <set>
//#include <map>
//#include <queue>
//#include <bitset>
//#include <math.h>
using namespace std ;
//using ll = long long ;
//using ld = long double ;
//using vll = vector<ll> ;
//using vvll = vector<vll> ;
//using vc = vector<char> ;
//using vvc = vector<vc> ;
//using vb = vector<bool> ;
//using vvb = vector<vb> ;
//using pll = pair<ll,ll> ;

//ll mod = 1000000007 ;
//long double pie = acos(-1) ;

string yorn(bool a){if(a) return"Yes" ; return "No" ;}
//string YorN(bool a){if(a) return"YES" ; return "NO" ;}
//ll gcd(long long a,long long b){if(b==0) return a ; return gcd(b,a%b) ;}
//ll lcm(long long a,long long b){return a/gcd(a,b)*b ;}
//ll sa(long long a,long long b){if(a>b) return a-b ; return b-a ;}
//void mysort(vector<long long> &a){sort(a.begin(),a.end()) ;}
//void myrev(vector<long long> &a){reverse(a.begin(),a.end()) ;}

int main(){
	int a,b,c ;
	cin >> a >> b >> c ;
	cout << yorn(a==b&&b==c) << endl ;
}


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

using namespace std;

typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> VI;
typedef vector<VI> VVI;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = numeric_limits<int>::max() / 2;
const int NEG_INF = numeric_limits<int>::min() / 2;

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

  int g[10]={1,2,4,8,16,32,64,128,256,512};
  int n;
  while(cin>>n){
      std::vector<int> v;
      for(int i=9;i>=0;i--){
          if(n>=g[i]){
              v.push_back(g[i]);
              n-=g[i];
          }
      }
      sort(v.begin(),v.end());
      for(int i=0;i<(int)v.size();i++){
          if(i!=(int)v.size()-1) cout<<v[i]<<" ";
          else cout<<v[i]<<endl;
      }
  }
}

Measured memory_bytes: 3092
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <deque>
#include <set>
#include <iomanip>
#include <utility>
typedef long long ll;
typedef long double ld;
using namespace std;

int main() {
	string S, T;
	cin >> S >> T;
	T.pop_back();
	if(S==T) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 3632
Q = int(input())

minl = 10**9
maxr = -1
ans_range = []
for _ in range(Q):
    l, r = map(int, input().split())
    ans_range.append((l, r))

    if l < minl:
        minl = l
    if r > maxr:
        maxr = r

dp = [0] * ((maxr - minl) + 2)

import math
for u in range(minl, maxr+1,1):
    check = (u + 1) / 2

    if not float.is_integer(check) or check == 1:
        dp[u - minl + 1] = dp[u-minl]
        continue

    ok = True
    for y in range(2, int(math.sqrt(check))+1):
        if check % y == 0:
            ok = False
            break

    ok2 = True
    for z in range(2, int(math.sqrt(u))+1):
        if u % z == 0:
            ok2 = False
            break
    
    if ok and ok2:
        # print("found: ", u)
        dp[u - minl + 1] = dp[u-minl] + 1
    else:
        # print("u:", u)
        dp[u - minl + 1] = dp[u-minl]

# print(dp)
for ll, rr in ans_range:
    if ll == rr:
        ans = dp[rr-minl+1] - dp[rr-minl]
    else:
        ans = dp[rr-minl+1] - dp[ll-minl]
    print(ans)

Measured memory_bytes: 23332
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

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


	int N = getint();
	int dp[3], h[3];
	dp[0] = 0;
	dp[1] = 1e9;
	dp[2] = 1e9;
	h[0] = getint();
	h[1] = getint();

	int k1 = 0;
	int k2 = 1;
	int k3 = 2;
	rep(i, N - 2) {
		h[k3] = getint();
		chmin(dp[k2], dp[k1] + abs(h[k1] - h[k2]));
		chmin(dp[k3], dp[k1] + abs(h[k1] - h[k3]));
		dp[k1] = 1e9;
		swap(k1, k2);
		swap(k2, k3);
	}
	chmin(dp[k2], dp[k1] + abs(h[k1] - h[k2]));

	printf("%d", dp[k2]);

	Would you please return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<long>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvb = vector<vector<bool>>;
using vvc = vector<vector<char>>;
using vvl = vector<vector<long>>;
using pii = pair<int, int>;
using pil = pair<int, long>;
using pll = pair<long, long>;
using vc = vector<char>;
#define fix20 cout << fixed << setprecision(20)
#define YES cout << "Yes" << endl
#define NO cout << "No" << endl
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define REP(i,s,t) for(int i=s; i<t; i++)
#define RNG(i,s,t,u) for(int i=s; i<t; i+=u)
#define MOD 1000000007
#define all(vec) vec.begin(), vec.end()



int main(){
  long a,b,c;
  cin >> a >> b >> c;
  long ans = 0;
  if(c >= a + b + 1){
    ans += a + b + 1 + b;
  }else{
    ans += b + c;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3592
#include<vector>
#include<list>
#include<algorithm>
#include<iostream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
int main(){
  int i;
  int a[256],m,n;
  char c,d;
  string s;
  while(cin>>n&&n){
    memset(a,0,sizeof(a));
    for(i=0;i<n;i++){
      cin>>c>>d;
      a[(int)c]=d;
    }
    cin>>m;
    s="";
    for(i=0;i<m;i++){
      cin>>c;
      s+=(char)(a[(int)c]?:c);
    }
    cout<<s<<endl;
  }
  return 0;
}

Measured memory_bytes: 1116
local fst, snd = io.read(2, 2)
fst = tonumber(fst)
snd = tonumber(snd)
local yymm, mmyy = true, true
if fst >= 13 or fst <= 0 then
    mmyy = false
end
if snd >= 13 or snd <= 0 then
    yymm = false
end
if yymm and mmyy then
    print("AMBIGUOUS")
elseif yymm then
    print("YYMM")
elseif mmyy then
    print("MMYY")
else
    print("NA")
end

Measured memory_bytes: 1008
#include <bits/stdc++.h>
using namespace std;
int main() {
    string w, t, T;
    cin >> w >> t;

    int sumA = 0;
    smatch m;
    regex re("\\b" + w + "\\b", regex_constants::icase);
    while (t != "END_OF_TEXT") {
        if (regex_search(t, m, re)) {
            sumA++;
        }
        cin >> t;
    }
    cout << sumA << endl;
    return 0;
}



Measured memory_bytes: 3268
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;
template <typename T> using vec = std::vector<T>;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int main() {
    ll A, B;
    cin >> A >> B;
    ll G = gcd(A,B);

    map<ll, ll> ps;
    auto decompositPrime = [&](ll n, map<ll, ll> &mp) {
        ll a = 2;
        while (n >= a * a) {
            if (n % a == 0) {
                mp[a]++;
                n /= a;
            } else {
                a++;
            }
        }
        if (n != 1) mp[n]++;
    };

    decompositPrime(G, ps);
    
    ll ans =1;
    for (auto [e0,e1] : ps) {
        ++ans;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3632
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
using Library;
using static Library.Input;

namespace AtCoderTemplate
{
    class ProgramA
    {
        static void Main()
        {
            var s = Console.ReadLine();
            var array = Enumerable.Repeat(0L, s.Length + 1).ToArray();

            for (int i = 0; i < s.Length; i++)
            {
                if (s[i] == '<')
                {
                    array[i + 1] = array[i] + 1;
                }
            }

            for (int i = s.Length - 1; i >= 0 ; i--)
            {
                if (s[i] == '>')
                {
                    array[i] = Math.Max(array[i + 1] + 1, array[i]);
                }
            }

            // System.Console.WriteLine(string.Join(" ", array));
            System.Console.WriteLine(array.Sum());
        }
    }
}

namespace Library
{
    class Input
    {
        static IEnumerator<string> enumerator = new string[] { }.AsEnumerable().GetEnumerator();

        public static string Line => Console.ReadLine();

        public static string[] StrArr => Line.Split(' ');

        public static int NextInt => int.Parse(NextWord());

        public static long NextLong => long.Parse(NextWord());

        public static List<int> IntList => StrArr.Select(int.Parse).ToList();

        public static List<long> LongList => StrArr.Select(long.Parse).ToList();

        public static IEnumerable<long[]> TakeLine(int N)
        {
            return Enumerable.Repeat(0, N).Select(_ => Console.ReadLine().Split(' ').Select(long.Parse).ToArray());
        }

        public static string NextWord()
        {
            while (!enumerator.MoveNext())
            {
                enumerator = StrArr.AsEnumerable().GetEnumerator();
            }
            return enumerator.Current;
        }
    }
}


Measured memory_bytes: 24928
// E - Strings of Impurity
#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[])
{
	string s, t;
	cin >> s >> t;

	set<char> x;
	for (int i = 0; i < s.size(); i++) x.insert(s[i]);
	bool failed = false;
	for (int i = 0; i < t.size(); i++)
		if (x.count(t[i]) == 0)
			failed = true;
	if (failed) {
		cout << -1 << endl;
		return 0;
	}

	x.clear();
	for (int i = 0; i < t.size(); i++) x.insert(t[i]);

	vector<vector<int> > p(256);
	for (int i = 0; i < s.size(); i++)
		if (x.count(s[i]) > 0)
			p[s[i]].push_back(i);

	long long ans = 0;
	for (int i = 0, j = -1, jj = -1; i < t.size(); i++) {
		j++;
		vector<int> &z = p[t[i]];
		vector<int>::iterator it = lower_bound(z.begin(), z.end(), j);
		j = it != z.end() ? *it : *z.begin();
		ans += j - (jj >= 0 ? jj : 0);
		if (j <= jj) ans += s.size();
		jj = j;
	}

	cout << ans + 1 << endl;

	return 0;
}


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

//00:15

int T,N;
int cycle[31];
int day[301];
int dp[301][31];
int dfs(int x,int t){
	if( x == 300 ) return 0;
	if( dp[x][t] != -1 ) return dp[x][t];
	int ans = dfs(x+1,1%T) + 1;
	if( cycle[t] <= day[x] ){
		ans = min(ans,dfs(x+1,(t+1)%T));
	}
	return dp[x][t] = ans;
}

int main(){
	while( cin >> T && T ){
		memset(dp,-1,sizeof(dp));
		for(int i = 0 ; i < 301 ; i++) 
			day[i] = 1e9;
		for(int i = 0 ; i < T ; i++){
			cin >> cycle[i];
		}
		cin >> N;
		for(int i = 0 ; i < N ; i++){
			int d,m;
			cin >> d >> m;
			d--;
			day[d] = min(day[d],m);
		}
		cout << dfs(0,0) << endl;
	}
}

Measured memory_bytes: 1216
#include <iostream>

using namespace std;

int main() {
	// input number of information
	int n;
	cin >> n;

	// input information
	int *array = new int[ 4 * 3 * 10 ];
	for( int i = 0; i < n; i++ ) {
		int b, f, r, v;
		cin >> b >> f >> r >> v;
		array[ ( b - 1 ) * 3 * 10 + ( f - 1 ) * 10 + ( r - 1 ) ] += v;
	}

	// output
	for( int idx_b = 0; idx_b < 4; idx_b++ ) {
		for( int idx_f = 0; idx_f < 3; idx_f++ ) {
			for( int idx_r = 0; idx_r < 10; idx_r++ ) {
				cout << " " << array[ idx_b * 3 * 10 + idx_f * 10 + idx_r ];
			}
			cout << endl;
		}
		if( idx_b != 3 ) {
			cout << "####################" << endl;
		}
	}
}


Measured memory_bytes: 3064
N = gets.to_i
ts = gets.split.map(&:to_f)
vs = gets.split.map(&:to_f)

ts2 = ts.reduce([0]) { |memo, t| memo + [memo.last + t] }
T = ts2.last
fs = [-1, *ts2, T + 1].each_cons(2).zip([0.0, *vs, 0.0])

ws = 0.step(T, 0.5).map do |t|
  fs.map do |(l, r), v|
    if t < l
      v + (l - t)
    elsif t <= r
      v
    else
      v + (t - r)
    end
  end.min
end

ans = ws.each_cons(2).map { |w1, w2| w1 + w2 }.reduce(&:+) * 0.25
puts format('%.15f', ans)


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

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(int i=0;i<n;++i)
#define ALL(name) name.begin(),name.end()
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
#define MAX_N 30010

int N;
string S;
int ans = 0;

// i より後ろにある、一番近い j の位置を返す
int pos[MAX_N][20];

void dfs(int i, int cnt) {
    if(cnt >= 3) {
        ans++;
        return;
    }
    if(cnt == 0) {
        assert(i == 0);
        REP(next_i, 11) {
            if(next_i == S[i] - '0') {
                dfs(0, cnt + 1);
            }
            else if(pos[i][next_i] != -1) {
                assert(i < pos[i][next_i]);
                dfs(pos[i][next_i], cnt + 1);
            }
        }
    }
    else {
        REP(next_i, 11) {
            if(pos[i][next_i] != -1) {
                assert(i < pos[i][next_i]);
                dfs(pos[i][next_i], cnt + 1);
            }
        }
    }
}

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

    cin >> N >> S;

    MINUS(pos);
    REP(j, 11) {
        int tmp = -1;
        for(int i = N - 1; i >= 0; --i) {
            pos[i][j] = tmp;
            if(S[i] - '0' == j) {
                tmp = i;
            }
        }
    }

    dfs(0, 0);

    printf("%lld\n", ans);

    return 0;
}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
#define FI(i, a, b) for (int i = (a); i <= (b); ++i)
#define FD(i, a, b) for (int i = (b); i >= (a); --i)
#define DEBUG(x) cerr << #x << ": " << (x) << '\n';

const int N = 105;
int n;
pair<int, int> pv[N];

int main() {
  cin >> n;
  FI(i,1,n) scanf("%d%d", &pv[i].first, &pv[i].second);
  sort(pv + 1, pv + 1 + n, [](const pair<int, int> x, const pair<int, int> y) {
      return atan2(x.second, x.first) < atan2(y.second, y.first);
  });
  double ans = 0;
  for (int i = 1; i <= n; ++i) {
    LL sumx = 0, sumy = 0;
    for (int len = 0; len < n; ++len) {
      int j = (i + len - 1) % n + 1;
      sumx += pv[j].first, sumy += pv[j].second; 
      ans = max(ans, sqrt(sumx * sumx + sumy * sumy));
    }
  }
  printf("%.10f\n", ans);
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<vector>
#include<cmath>
#include<cstring>
#include<cstdio>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define rp(a) while(a--)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
const double PI=acos(-1);
const double EPS=1e-10;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
bool h[9][9]={
	{0,1,0,1,0,0,0,0,0},
	{1,0,1,0,1,0,0,0,0},
	{0,1,0,0,0,1,0,0,0},
	{1,0,0,0,1,0,1,0,0},
	{0,1,0,1,0,1,0,1,0},
	{0,0,1,0,1,0,0,0,1},
	{0,0,0,1,0,0,0,1,0},
	{0,0,0,0,1,0,1,0,1},
	{0,0,0,0,0,1,0,1,0}
};
int main(){
	string s;
	rep(i,1000){
		cin>>s;
		bool ans=true;
		rep(j,s.size()-1)if(!h[s[j]-'A'][s[j+1]-'A']){
			ans=false;
			break;
		}
		if(ans)cout<<s<<endl;
	}
}

Measured memory_bytes: 1172
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 202000;const ll inf = 1e16;
int n,a[N],T;ll f[N],q[N];int p[N];
bool isright(int i, int j){return T-2LL*(a[j-1]-a[i])<0;}
int main() {
	read(n);read(a[n+1]);read(T);
	rep(i,1,n)read(a[i]);
	ll x=inf;int F=1,R=1;
	for(int i=n,j=n+2;i>=1;i--){
		f[i]=inf;
		while(j-1>i+1&&isright(i,j-1)){
			j--;if(F!=R&&p[F]==j)F++;
			umin(x,f[j]+2*a[j-1]+a[j]);
		}
		if(isright(i,i+1))j=i+1,umin(x,f[j]+2*a[j-1]+a[j]);
		else{
			ll val=f[i+1]+a[i+1];
			while(F!=R&&q[R-1]>=val)R--;p[R]=i+1;q[R++]=val;
		}
		if(F!=R)umin(f[i],q[F]+T-a[i]);umin(f[i],x-3LL*a[i]);
		//rep(j,i+1,n+1)umin(f[i],f[j]+2*(a[j-1]-a[i])+a[j]-a[i]+max(0,T-2*(a[j-1]-a[i])));
	}
	cout<<f[1]+a[1];
	return 0;
}


Measured memory_bytes: 3712
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cfloat>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits.h>
#include <list>
#include <map>
#include <math.h>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define int long long
#define ll long long
#define eps LDBL_EPSILON
#define mod (ll)1000000007
#define INF LLONG_MAX/10
#define P pair<int,int>
#define prique priority_queue
using namespace std;
int n;
set<int> st;
signed main() {
	cin >> n;
	if (n == 3) {
		cout << 2 << " " << 3 << " " << 25 << endl;
		return 0;
	}
	if (n == 4) {
		cout << 2 << " " << 3 << " " << 25 << " " << 30 << endl;
		return 0;
	}
	st.insert(2);
	st.insert(3);
	st.insert(25);
	st.insert(30);
	int cnt = n - 4;
	for (int i = 30;; i += 30) {
		if (st.find(i) == st.end() && i <= 30000) {
			st.insert(i);
			cnt--;
			if (!cnt)break;
		}
		for (int j = i / 2 - 14; j < i / 2; j++) {
			if (st.find(j) != st.end() || st.find(i - j) != st.end())continue;
			if (cnt >= 2 && (j % 2 == 0 || j % 3 == 0 || j % 5 == 0)) {
				st.insert(j); st.insert(i - j);
				cnt -= 2;
				if (cnt == 1) {
					st.erase(--st.end());
					cnt++;
				}
				if (!cnt)goto kaage;
			}
		}
	}
kaage:;
	for (auto ite = st.begin(); ite != st.end(); ite++) {
		if (++ite == st.end()) {
			cout << *(--ite) << endl;
		}
		else cout << *(--ite) << " ";
	}
	return 0;
}

Measured memory_bytes: 1280
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <sstream>
#include <queue>
#include <deque>
#define ll long long
#define MP make_pair
#define PII pair<int, int>
#define F first
#define S second
using namespace std;
string s,ss;
int main()
{
	cin >>s>>ss;
	if (ss.size()>s.size())
	{	
		cout <<"UNRESTORABLE";
		return 0;
	}
	for (int i=s.size()-ss.size();i>=0;i--)
	{
		bool fl=1;
		for (int j=0;j<ss.size();j++)
		{
			if (s[i+j]=='?') continue;
			if (s[i+j]!=ss[j])
			{
				fl=0;
				break;
			}
		}
		if (fl)
		{
		    for (int j=0;j<ss.size();j++) if (s[i+j]=='?') s[i+j]=ss[j];
		    for (int j=0;j<s.size();j++) if (s[j]=='?') s[j]='a';
		    cout <<s;
		    return 0;
		}
	}
	cout <<"UNRESTORABLE";
	return 0;
}


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

struct Edge {
  int v, w;
};
typedef vector<vector<Edge> > Graph;

const int MAXN = 6000;
int cap, src, dst;
Graph G;
bool lpg[MAXN];
map<string, int> id;

void init() {
  id.clear();
  G.clear();
  memset(lpg, 0, sizeof(lpg));
}

int get_id(const string &s) {
  if (!id.count(s)) {
    int tmp = id.size();
    id[s] = tmp;
  }
  return id[s];
}

void add_edge(int a, int b, int w) {
  if (G.size() <= max(a, b)) {
    G.resize(max(a, b) + 1);
  }
  G[a].push_back((Edge){b, w});
  G[b].push_back((Edge){a, w});
}

struct State {
  int v, gas, w;
  bool operator < (const State &s) const {
    return w > s.w;
  }
};

int dijkstra() {
  const static int INF = 1<<28;
  int N = G.size();
  vector<vector<int> > cost(N, vector<int>(cap + 1, INF));
  priority_queue<State> que;
  cost[src][cap] = 0;
  que.push((State){src, cap, 0});
  while (que.size()) {
    const State s = que.top();
    que.pop();
    if (cost[s.v][s.gas] < s.w) continue;
    if (s.v == dst) return s.w;
    for (int i = 0; i < G[s.v].size(); ++i) {
      const Edge &e = G[s.v][i];
      if (s.gas - e.w < 0) continue;
      const State t = {e.v,
                       lpg[e.v] ? cap : s.gas - e.w,
                       s.w + e.w};
      if (cost[t.v][t.gas] <= t.w) continue;
      cost[t.v][t.gas] = t.w;
      que.push(t);
    }
  }
  return -1;
}

int main() {
  for(int n, m; cin >> n >> m >> cap && (n|m|cap); ) {
    cap *= 10;
    init();
    string s, t;
    cin >> s >> t;
    src = get_id(s);
    dst = get_id(t);
    for (int i = 0, w; i < n; ++i) {
      cin >> s >> t >> w;
      add_edge(get_id(s), get_id(t), w);
    }
    for (int i = 0; i < m; ++i) {
      cin >> s;
      lpg[get_id(s)] = true;
    }
    cout << dijkstra() << endl;
  }
  return 0;
}

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

using i64 = long long;
using P = pair<i64, i64>;

#define overload3(_1, _2, _3, name, ...) name
#define rep1(i, n) for(i64 i = 0LL; i < (n); ++i)
#define rep2(i, a, b) for(i64 i = (a); i < (b); ++i)
#define rep(...) overload3(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
#define all(v) v.begin(), v.end()


void solve(long long K, long long A, long long B){
    for(int i = K; i <= B; i += K){
        if(A <= i && i <= B){
            cout << "OK" << endl;
            return;
        }
    }
    cout << "NG" << endl;
}

struct IoSetup {
    IoSetup() {
        // cin.tie(nullptr);
        // ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
        cerr << fixed << setprecision(10);
    }
} iosetup;

int main(){
    long long K;
    scanf("%lld",&K);
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    solve(K, A, B);
    return 0;
}


Measured memory_bytes: 3700
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int inf=1e9+7;
int N,A,B,C;
int l[8];
int dfs(int cur,int a,int b,int c){
    if(cur==N){
        if(a==0||b==0||c==0) return inf;
        return abs(A-a)+abs(B-b)+abs(C-c)-30;
    }
    int r0,r1,r2,r3;
    r0=dfs(cur+1,a,b,c);
    r1=dfs(cur+1,a+l[cur],b,c)+10;
    r2=dfs(cur+1,a,b+l[cur],c)+10;
    r3=dfs(cur+1,a,b,c+l[cur])+10;
    return min({r0,r1,r2,r3});
}
int main(){
    cin>>N>>A>>B>>C;
    for(int i=0;i<N;i++) cin>>l[i];
    cout<<dfs(0,0,0,0)<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>
#include<utility>

using namespace std;

#define int long long
#define endl "\n"

constexpr long long INF = (long long)1e18;
constexpr long long MOD = 1'000'000'007; 

struct fast_io {
	fast_io(){
		std::cin.tie(nullptr);
		std::ios::sync_with_stdio(false);
	};
} fio;

class union_find
{
	int  _setnum;
	vector<int> par, nume;
public:
	union_find(){
	}
	
	union_find(int x){
		par.resize(x);
		nume.resize(x);
		init();
	}
	
	~union_find(){
		//
		
	}
	
	void clear(){
		_setnum = 0;
		par.clear();
		nume.clear();
	}
	
	void init(){
		_setnum = par.size();
		for(int i = 0; i < par.size(); i++){
			par[i] = i;
			nume[i] = 1;
		}
	}
	
	void resize(int x){
		
		par.resize(x);
		nume.resize(x);
		init();
	}

	int find(int x){
		return par[x] == x ? x : par[x] = find(par[x]);
	}

	void unite(int x, int y){
		x = find(x);
		y = find(y);
	
		if(x == y)return;
		
		_setnum--;
		
		if(nume[x] > nume[y]) std::swap(x,y);
		
		par[x] = y;
		nume[y] += nume[x];
	}
	
	bool same(int x, int y){
		return find(x) == find(y);
	}
	
	int numel(int x){
		return nume[find(x)];
	}
	
	int size(){
		return par.size();
	}
	
	int setnum(){
		return _setnum;
	}
};

signed main(){
	cout<<fixed<<setprecision(10);
	
	int N, M;
    union_find uf;
    
    cin>>N>>M;
	
    uf.resize(N);
    
    for(int i = 0; i < M; i++){
        int A, B;
        
        cin>>A>>B;
        
        A--, B--;
        
        uf.unite(A, B);
    }
    
    int ans = 0;
    
    for(int i = 0; i < N; i++){
        ans = max(ans, uf.numel(i));
    }
    
    cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 5976
#include <iostream>
using namespace std;
typedef long long ll;
ll f(ll n){
    ll p=1;
    ll mod=1000000007;
    for(int i=1;i<=n;i++){
        p=p*i%mod;
    }
    return p;
}
int main(void){
    // Your code here!
    ll mod=1000000007;
    int n,m;
    cin>>n>>m;
    if(n==m)cout<<f(n)*f(m)*2%mod<<endl;
    
    else if (n==m+1 || m==n+1) cout<<f(n)*f(m)%mod<<endl;
    else cout<<0<<endl;
}


Measured memory_bytes: 256
#include<stdio.h>
void merge(int *,int,int,int);
void mergeSort(int *,int,int);
int S[500000],count=0;
int main(){
  int i,j,n;
  scanf("%d",&n);
  for(i=0;i<n;i++)
    scanf("%d",&S[i]);
  mergeSort(S,0,n);
  for(i=0;i<n;i++){
    if(i>0) printf(" ");
    printf("%d",S[i]);
  }
  printf("\n%d\n",count);
  return 0;
}
  
void merge(int A[],int left,int mid,int right){
  int n1=mid-left,n2=right-mid,i,L[n1+1],R[n2+1],j,k;
  for(i=0;i<=n1-1;i++){
    L[i]=A[left+i];
  }
  for(i=0;i<=n2-1;i++){
    R[i]=A[mid+i];
  }
  L[n1]=1000000000;
  R[n2]=1000000000;
  i=0;
  j=0;
  for(k=left;k<=right-1;k++){
    if(L[i]<=R[j]){
      A[k]=L[i];
      i=i+1;
    }
      
    else{
      S[k]=R[j];
      j=j+1;
    }
    count++;
  }
}
void mergeSort(int S[],int left,int right){
  int mid;
  if(left+1<right){
    mid=(left+right)/2;
    mergeSort(S,left,mid); 
    mergeSort(S,mid,right);
    merge(S,left,mid,right);
  }
}
    

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

using namespace std;

int gcd(int n, int m) {
  while (m) {
    auto t = n % m;
    n = m;
    m = t;
  }
  return n;
}

int main(int ac, char **av) {
  int n, m;
  while (cin >> n >> m, n) {
    cout << gcd(n, m) << endl;
    n = m = 0;
  }
  return 0;
}

Measured memory_bytes: 3072
#include<iostream>
#include<vector>
#include<string>

#define rep(i, n) for(int i = 0; i < (n); i++)
using ll = long long;
const ll mod = 1000000007;

int main(){
	int N;
	std::cin >> N;
	std::vector<ll> A(N);
	std::vector<ll> c(N);
	rep(i, N) std::cin >> A[i];

	if(N == 2){
		std::cout << A[0] * A[1] % mod << std::endl;
		return 0;
	}

	c[N-2] = A[N-1];
	for(int i=N-3; i>=0; i--){
		c[i] = c[i+1] + A[i+1];
		c[i] %= mod;
	}

	ll res = 0;
	rep(i, N-1){
		res += (A[i] * c[i]);
		res %= mod;
	}
	std::cout << res << std::endl;
	return 0;
	
}

Measured memory_bytes: 6364
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(int I = int(A); I < int(B); ++I)
#define FORR(I,A,B) for(int I = int((B)-1); I >= int(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#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
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;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 NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=1e18+7;
const ll MOD=1e9+7;
#define pri(a) cout << (a) << endl


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

	ll N;
	cin >> N;
	ll dp[N+3][3]={};
	FOR(i,1,N+1){
		ll a,b,c;
		cin >> a >> b >> c;
		dp[i][0] = max(dp[i-1][1],dp[i-1][2])+a;
		dp[i][1] = max(dp[i-1][0],dp[i-1][2])+b;
		dp[i][2] = max(dp[i-1][1],dp[i-1][0])+c;
	}
	cout << max({dp[N][0],dp[N][1],dp[N][2]}) << endl;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)

lint N, A, B;

int main()
{
    cin >> N >> A >> B;
    if (A > B) cout << 0 << endl;
    else if (N == 1 and A < B) cout << 0 << endl;
    else cout << (B * (N - 1) + A) - (A * (N - 1) + B) + 1 << endl;
}


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

bool solve() {
    ll N, M, K;
    cin >> N >> M >> K;
    for ( int i = 0; i <= N; i++ ) {
        for ( int j = 0; j < M; j++ ) {
            if ( i*j + (N-i)*(M-j) == K) return true;
        }
    }
    return false;
}

int main() {
    string ans = solve() ? "Yes" : "No";
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 256
n=int(input())
k=0
l=0
for i in range(n):
    a,b=input().split()
    mylist=[a,b]
    newlist=sorted(mylist)
    if a !=b:
        if newlist[1]==a:
            k+=3
        if newlist[1]==b:
            l+=3
    else:
        k+=1
        l+=1
    
print(k,l)




Measured memory_bytes: 5604