akhauriyash/Code-Regression huggingface dataset:
def answer(price, flag):
    if flag == True:
        price //= 2
        if price % 50 != 0:
            price += price % 50
        print(price)
    else:
        print(price)


table = [[0, 300, 500, 600, 700, 1350, 1650], [6, 0, 350, 450, 600, 1150, 1500],
         [13, 7, 0, 250, 400, 1000, 1350], [18, 12, 5, 0, 250, 850, 1300],
         [23, 17, 10, 5, 0, 600, 1150], [43, 37, 30, 25, 20, 0, 500],
         [58, 52, 45, 40, 35, 15]]

while 1:
    d = int(input())
    if d == 0:
        break

    h1, m1 = map(int, input().split())
    a = int(input())
    h2, m2 = map(int, input().split())

    start = min(d, a) - 1
    end = max(d, a) - 1
    dis = table[end][start]
    price = table[start][end]

    if dis > 40:
        answer(price, False)
        continue
    else:
        if h1 == 18 or h2 == 18:
            answer(price, True)
            continue
        if h1 == 17 and m1 >= 30:
            answer(price, True)
            continue
        if h2 == 17 and m2 >= 30:
            answer(price, True)
            continue
        if h1 == 19 and m1 <= 30:
            answer(price, True)
            continue
        if h2 == 19 and m2 <= 30:
            answer(price, True)
            continue
        answer(price, False)


Measured memory_bytes: 5612
#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
#define int long long
using namespace std;
typedef pair<int,int>P;
typedef pair<P,int>P2;
#define fi first
#define se second

typedef unsigned long long ull;


struct RollingHash{
  typedef unsigned long long ull;
  string S;
  ull B;
  int len;
  vector<ull> hash,p;
  RollingHash(){}
  RollingHash(string S_,ull B_=1000000009LL):
    S(S_),B(B_),len(S.length()),hash(len+1),p(len+1){
    hash[0]=0;p[0]=1;
    for(int i=0;i<len;i++){
      hash[i+1]=hash[i]*B+S[i];
      p[i+1]=p[i]*B;
    }
  }
  //S[l,r)
  ull find(int l,int r){
    return hash[r]-hash[l]*p[r-l];
  }
};

signed main(){
  int n;
  cin>>n;
  string s;
  cin>>s;
  string t=s;

   set<char>st;
  r(i,n){
    st.insert(s[i]);
  }

  reverse(t.begin(),t.end());

  if(st.size()==1){
    cout<<2<<endl;
    return 0;
  }

  RollingHash S(s);
  RollingHash T(t);

  for(int i=2;i<=n;i++){

    int idx=0 , F=0 ;
    ull A=S.find(0,i);

    for(int j=0;;j++){

      if(j%2==0){

        if(idx+i>n){//cout<<j<<endl;
          int x=n-idx;
          ull has=S.find(0,x);

          if(S.find(idx,n)!=has){
            F++;
            break;
          }
        }

        else{
        if(S.find(idx,idx+i) != A){
          F++;
          break;
        }}
      }

      else{

        if(n-idx-i<0){

          ull has=S.find(i-(n-idx),i);

          //cout<<i-n-idx<<' '<<i<<endl;

          if(T.find(0,n-idx)!=has){
            F++;
            break;
          }
        }

        else{
        if(T.find(n-idx-i,n-idx) != A){
          //cout<<n-idx-i<<' '<<n-idx<<endl;
          F++;
          break;
        }}
      }

      idx+=i-1;

      //cout<<idx<<endl;

      if(idx>n)break;
    }

    //cout<<idx<<' '<<i<<endl;
    if(!F){

      cout<<i<<endl;
      return 0;

    }
  }

}



Measured memory_bytes: 39200
#include <bits/stdc++.h>
typedef long long LL;
#define SORT(c) sort((c).begin(),(c).end())

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

using namespace std;
int main(void)
{
  int n;
  cin >> n;
  vector<vector<int> > C;
  C.resize(n);
  REP(i,n) C[i].resize(n);
  REP(i,n) REP(j,n) cin >> C[i][j];
  LL ans=0;
  REP(i,n) REP(j,n) if(i<j) ans+=min(C[i][j],C[j][i]);
  cout << ans << endl;
  return 0;
}

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

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x,y) (lower_bound(all(x),y)-x.begin())
#define ubd(x,y) (upper_bound(all(x),y)-x.begin())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }

typedef long long ll; 
typedef long double ld;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
typedef pair<ll,ll>pi; typedef pair<ll,pi>spi; typedef pair<pi,pi>dpi;

#define LLINF ((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (1000006)
ll n,f[MAXN],inv[MAXN],mod=1e9+7,ans;
int main(){
	FAST
	cin>>n;
	auto qexp=[&](ll x,ll e){
		ll sum=1;
		while(e){
			if(e&1) sum*=x, sum%=mod;
			x*=x,x%=mod;
			e>>=1;
		}
		return sum;
	};
	auto C=[&](ll n,ll k){
		return n < k ? 0 : f[n]*inv[k]%mod*inv[n-k]%mod;
	};
	f[0]=1; FOR(i,1,MAXN-1) f[i]=f[i-1]*i%mod;
	inv[MAXN-1] = qexp(f[MAXN-1], mod-2); DEC(i,MAXN-2,0) inv[i]=inv[i+1] * (i+1) % mod;
	FOR(k,2,n-2){
		ans -= C(k-1,n-k-1) * f[k] % mod * f[n-1-k] % mod, ans += mod, ans %= mod;
	}
	ans += f[n-1] * (n-1) % mod, ans %= mod;
	cout<<ans<<'\n';
}


Measured memory_bytes: 15872
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <set>
#include <algorithm>
#include <map>

using namespace std;

int main(){
    int n, m, c;
    cin >> n >> m >> c;
    int b[m];
    for (int i = 0; i < m; ++i) {
        cin >> b[i];
    }
    int cnt = 0;
    for(int i = 0; i < n; ++i){
        int sum = 0;
        for (int j = 0; j < m; ++j) {
            int x;
            cin >> x;
            sum += x * b[j];
        }
        sum += c;
        cnt += (sum > 0);
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define lp(i,n) for(int i=0;i<n;i++)
int ls[10][10];

char calc(string s){
  //cout<<s<<endl;
  int now=0;
  lp(i,4){
    int to=s[i]-'0';
    now=ls[now][to];
  }
  char c=now+'0';
  return c;
}

bool tr(string s){
  int now=0;
  lp(i,5){
    int to=s[i]-'0';
    now=ls[now][to];
  }
  if(now==0)return true;
  return false;
}


bool check(int x){
  string base="";
  lp(i,4){
    int num=x%10;
    x/=10;
    char c=num+'0';
    base=c+base;
  }

  string ch=base+calc(base);
  //cout<<" "<<base<<endl;
  lp(i,5){
    lp(j,10){
      string s=ch;
      s[i]='0'+j;
      if(s==ch)continue;
      if(tr(s))return false;
    } 
  }
  lp(i,4){
    string s=ch;
    swap(s[i],s[i+1]);
    if(s==ch)continue;
    if(tr(s))return false;
  }
  return true;
}

int main(){
  lp(i,10){
    lp(j,10){
      cin>>ls[i][j];
    }
  }
  int ans=10000;
  for(int i=0;i<10000;i++){
    if(check(i))ans--;
  }
  cout<<ans<<endl;
  return 0; 
}



Measured memory_bytes: 3216
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        if(0 < a && a < 10 && 0 < b && b < 10) System.out.println(a*b);
        else System.out.println(-1);
        sc.close();

    }

}


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

int main(void){
    int h, w;
    cin >> h >> w;
    
    char a[100][102];
    int i;
    for(i = 0; i < h; i++){
        cin >> a[i];
    }
    
    int j;
    for(j = 1; j <= w + 2; j++){
        cout << '#';
    }
    cout << endl;
    
    for(i = 0; i < h; i++){
        cout << '#' << a[i] << '#' << endl;
    }
    
    for(j = 1; j <= w + 2; j++){
        cout << '#';
    }
    cout << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
/*
変更箇所は順読み逆読みの少なくとも片方で役立たないといけない
つまり1点分として加算される必要がある
逆に1点分以上の役割は持てない<-嘘だった
例えば右端の文字が他に存在しない文字ならそれを変更するのはOK
*/
/*
問題概要は最長の回文を作れ？
だとすると中心決めてしまえばそこからは書き換えるかどうかは片側だけに注目すればよくて
sBtに対してsを右側から見ていくことを考える
変えるならt[now]しかありえなくて、書き換えた方がいいかどうかチェックするのに150^2かかる？
なんか違いそう
端から見て言ってdp[i][j][k]で考えるべき？
dp[i][j][k]:左からi文字右からj文字、k文字変更した時の最長回文
dp[i][j][k]=max(dp[i][j-1][k],dp[i-1][j][k],dp[i-1][j-1][k]+(s[i]==s[N-j-1]),dp[i-1][j-1][k-1]+1)
*/
int dp[400][400][400];
signed main(){
  string s;int K;cin>>s>>K;
  int N=s.size();
  int ans=1;
  for(int k=0;k<=K;k++){
    for(int i=1;i<N;i++){
      for(int j=1;i+j<=N;j++){
        dp[i][j][k]=max({dp[i][j-1][k],dp[i-1][j][k],dp[i-1][j-1][k]+2*(s[i-1]==s[N-j])});
        if(k)dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k-1]+2);
        ans=max(ans,dp[i][j][k]+(i+j<N));
      }
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 187776
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(ll i = 0; i < (n); ++i)
#define repA(i, a, n) for(int  i = a; i <= (n); ++i)
#define all(x) x.begin(), x.end()
#define sz(x) (int) (x).size()
#define fill(a) memset(a, 0, sizeof(a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
#define endl '\n'
#define init(n) int n;cin>>n;int a[n];rep(i,n)cin>>a[i];
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long long int> vll;
typedef vector<pii> vii;
ll p=998244353 ;
ll add(ll a,ll b){
    ll t=(a+b);
    if(t>=p)t-=p;
        return t;
}
ll sub(ll a,ll b){
    ll t=a-b+p;
    t=t%p;
    return t;
}
ll power(ll a,ll x){
    if(x<0)return 1;
    ll r=1;
    while(x!=0){
        if(x%2==1){
            r=r*a;r%=p;
        }
        a=a*a;a%=p;
        x=x/2;
    }
    return r;
}
ll mul(ll a,ll b){
    ll t=(a*b);
    if(t>=p)t%=p;
    return t;
}
map<int,int> m;
int rec(int i){
    if(i==1)return 0;
    if(m.find(i)!=m.end())return m[i];
    int x;
    if(i%2==0){
        x=1+rec(i/2);
    }
    else{
        x=1+rec(3*i+1);
    }
    m[i]=x;
    return x;
}
int getKth(int lo, int hi, int k) {
    int arr[1001];
    memset(arr,-1,sizeof(arr));
    pair<int,int> b[hi-lo+1];
    for(int i=1;i<=1000;i++){
        if(arr[i]==-1){
            rec(i);
        }
        arr[i]=m[i];
    }
    for(int i=lo;i<=hi;i++){
        b[i-lo].first=arr[i];
        b[i-lo].second=i;
    }
    sort(b,b+hi-lo+1);
    return b[k-1].second;
}
int main() {
  
    cin.sync_with_stdio(0); cin.tie(0);
    cin.exceptions(cin.failbit);
    int T=1;
    // cin>>T;
    while(T--){
        ll x,y,a,b,c;cin>>x>>y>>a>>b>>c;
        ll p[a+1],q[b+1],r[c+1];
        rep(i,a)cin>>p[i];
        rep(i,b)cin>>q[i];
        rep(i,c)cin>>r[i];
        sort(p,p+a,greater<ll>());
        sort(q,q+b,greater<ll>());
        sort(r,r+c,greater<ll>());
        ll ans=0;
        ll arr[x+y];
        rep(i,x)arr[i]=p[i];
        rep(i,y)arr[i+x]=q[i];
        sort(arr,arr+(x+y));
        for(int i=0;i<c;i++){
            if(arr[i]<r[i]){
                arr[i]=r[i];
            }
            else{
                break;
            }
        }
        rep(i,x+y){
            ans+=(arr[i]);
        }
        cout<<ans<<endl;
    }   
    return 0;   
}   


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

#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < n; i++)
#define vi vector<int>
#define vvi vector<vi>

using namespace std;

typedef long long ll;

int main() {
  int N, cnt2 = 0, cnt4 = 0;
  cin >> N;
  rep(i, N) {
    int a;
    cin >> a;
    if (a % 4 == 0) {
      cnt4++;
    } else if (a % 2 == 0) {
      cnt2++;
    }
  }
  string ans = "Yes";
  if (cnt2 == 0) {
    if ((N - 1) - cnt4 * 2 > 0) {
      ans = "No";
    }
  } else {
    if ((N - 1) - cnt4 * 2 - (cnt2 - 1) > 0) {
      ans = "No";
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define cinf(n,x) for(int i=0;i<(n);i++)cin>>x[i];
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define ft first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define mod 1000000007
using namespace std;
typedef long long ll;
template<class T> using V=vector<T>;
using Graph = vector<vector<int>>;
using P=pair<ll,ll>;
typedef unsigned long long ull;
typedef long double ldouble;
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; }
//V,P(大文字)使用不可

const ll INF=1000000000000000000;

signed main(){
    string s;
    cin>>s;
    int m=s.size();
    int ss=0;
    int cnt=0;
    for(int i=0;i<m;i++){
        if(s[i]=='S') ss++;
        else{
            if(ss>0){
                cnt++;
                ss--;
            }
        }
    }
    cout<<m-2*cnt<<endl;
}

Measured memory_bytes: 644
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		String S = s.nextLine();
		String T = s.nextLine();
		int count = 0;

		if (S.charAt(0) == T.charAt(0)) {
			count += 1;
		}
		if (S.charAt(1) == T.charAt(1)) {
			count += 1;
		}
		if (S.charAt(2) == T.charAt(2)) {
			count += 1;
		}
		System.out.println(count);
	}
}

Measured memory_bytes: 23892
import java.io.InputStream;
import java.io.PrintStream;
import java.util.*;

public class Main {

  public static void main(String[] args) {
    solve(System.in, System.out);
  }

  private static class Pair {
    int u;
    int v;
    long w;
  }

  static void solve(InputStream is, PrintStream os) {
    Scanner sc = new Scanner(is);

    /* read */
    int n = sc.nextInt();

    // u1 is always in white
    Set<Integer> white = new HashSet<>();

    Set<Integer> black = new HashSet<>();

    // u -> [(u, v, w), .. ]
    Map<Integer, List<Pair>> rslvs = new HashMap<>();

    for (int i = 0; i < n - 1; i++) {
      int u = sc.nextInt();
      int v = sc.nextInt();
      long w = sc.nextLong();

      List<Pair> list1 = rslvs.getOrDefault(u, new ArrayList<>());
      Pair p1 = new Pair();
      p1.u = u;
      p1.v = v;
      p1.w = w;
      list1.add(p1);
      rslvs.put(u, list1);

      List<Pair> list2 = rslvs.getOrDefault(v, new ArrayList<>());
      Pair p2 = new Pair();
      p2.u = v;
      p2.v = u;
      p2.w = w;
      list2.add(p2);
      rslvs.put(v, list2);
    }

    // 1 is always white.
    white.add(1);

    Queue<Integer> resolved = new LinkedList<>();
    resolved.add(1);
    while(!resolved.isEmpty()) {
      Integer r = resolved.remove();

      List<Pair> list = rslvs.get(r);

      for (Pair p : list) {
        // already visited
        if (white.contains(p.v) || black.contains(p.v)) {
          continue;
        }
        // u is white
        if (white.contains(p.u)) {
          if (p.w % 2 == 0) {
            white.add(p.v);
          } else {
            black.add(p.v);
          }
        } else { // u is black
          if (p.w % 2 == 0) {
            black.add(p.v);
          } else {
            white.add(p.v);
          }
        }
        resolved.add(p.v);
      }
    }

    for (int i = 1; i <= n; i++) {
      if (white.contains(i)) {
        os.println('0');
      } else {
        os.println('1');
      }
    }
  }
}

Measured memory_bytes: 131952
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

#define int long long

#define f first
#define s second

int setnum;
vector<int> par, siz;
vector<int> MST;

void init(int x){
  par.resize(x);
  siz.resize(x);
  setnum = x;
  
  for(int i = 0; i < x; i++){
    par[i] = i;
    siz[i] = 1;
  }
}

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

void unite(int x, int y){
  x =find(x);
  y = find(y);

  if(x == y) return;

  setnum--;

  if(siz[x] > siz[y]){
    siz[x] += siz[y];
    par[y] = x;
  } else {
    siz[y] += siz[x];
    par[x] = y;
  }
}

bool same(int x, int y){
  return find(x) == find(y);
}

signed main(){
  int N, M;
  int cost = 0, con = 0, mstc = 0;
  vector<pair<int,pair<int,int>>> edge, mst, edge2;

  cin>>N>>M;

  for(int i = 0; i < M; i++){
    int S, D, C;

    cin>>S>>D>>C;
    S--, D--;

    edge.push_back({C,{S,D}});
  }

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

  init(N);

  for(int i = 0; i < edge.size(); i++){
    if(!same(edge[i].s.f, edge[i].s.s)){
      unite(edge[i].s.f, edge[i].s.s);
      mst.push_back(edge[i]);
      mstc += edge[i].f;
    }
  }

  con = N-1;
  cost = mstc;
  
  for(int i = 0; i < mst.size(); i++){//
    int mstc2 = 0;
    edge2.clear();
    for(int j = 0; j < edge.size(); j++){
      if(mst[i] != edge[j]) edge2.push_back(edge[j]);
    }
    
    init(N);
    
    sort(edge2.begin(), edge2.end());
    
    for(int j = 0; j < edge2.size(); j++){
      if(!same(edge2[j].s.f, edge2[j].s.s)){
        unite(edge2[j].s.f, edge2[j].s.s);
        mstc2 += edge2[j].f;
      }
    }

    if(setnum == 1 && mstc2 == mstc){
      con--;
      cost -= mst[i].f;
    }

  }

  cout<<con<<" "<<cost<<endl;
  
  return 0;
}



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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<ll, pair<ll, ll> > P3;

const ll MOD = ll(1e9 + 7);
const ll LLINF = LLONG_MAX;
const int IINF = INT_MAX;
const int MAX_N = int(1e5) + 5;
const double EPS = 1e-8;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
#define SORT(v) sort((v).begin(), (v).end())
#define SORTR(v) sort((v).rbegin(), (v).rend())
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)


int main() {
    string s,t;
    cin >> s >> t;
    s += s;
    REP(i,t.size()){
        REP(j,t.size()){
            if(s[i+j]!=t[j])break;
            if(j==t.size()-1){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
h,w=map(int,input().split())

s=[input() for i in range(h)]

# def ok(i,j,houkou, count):
#     if i==h or j==w:
#         return count
#     elif s[i][j]=='#':
#         return count
#     elif houkou=='yoko':
#         return ok(i,j+1,houkou,count+1)
#     else:
#         return ok(i+1,j,houkou,count+1)

yoko=[[0 for i in range(w)] for j in range(h)]
tate=[[0 for i in range(w)] for j in range(h)]

count=0
for i in range(h):
    for j in range(w):
        if s[i][j]=='.':
            count+=1
        if s[i][j]=='#':
            for k in range(count):
                yoko[i][j-k-1]=count
            count=0
    if count>0:
        for k in range(count):
            yoko[i][j-k]=count
        count=0
# print(yoko)


for j in range(w):
    for i in range(h):
        if s[i][j]=='.':
            count+=1
        if s[i][j]=='#':
            for k in range(count):
                tate[i-k-1][j]=count
            count=0
    if count>0:
        for k in range(count):
            tate[i-k][j]=count
        count=0

# print(tate)

ans=0
for i in range(h):
    for j in range(w):
        if ans<yoko[i][j]+tate[i][j]-1:
            ans=yoko[i][j]+tate[i][j]-1
print(ans)


Measured memory_bytes: 126552
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) {
        try {
            // 標準入力
            InputStreamReader isr = new InputStreamReader(System.in);
            BufferedReader br = new BufferedReader(isr);
            int n = Integer.parseInt(br.readLine());
            int a[] = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = Integer.parseInt(br.readLine());
            }
            int now = a[0];
            int count = 1;
            boolean flag = false;
            while (count < n) {
                if (now == 2) {
                    System.out.println(count);
                    flag = true;
                    break;
                }
                now = a[now - 1];
                count++;
            }
            if (!flag) {
                System.out.println(-1);
            }
        } catch (IOException e) {
            e.printStackTrace();
           }
    }
}

Measured memory_bytes: 31888
#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1001001001
#define LINF 1001001001001001001
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define bit(n) (1LL<<(n))
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> LLP;

/*
  UnionFind Tree
*/
class UnionFind {
    private: 
        vector<int> par;
        vector<int> rank;
        vector<int> cnt;
    
    public:
        UnionFind(int n);
        int find(int x);
        void unite(int x, int y);
        bool same(int x, int y);
        int count(int x);
        void printStatus();
};

UnionFind::UnionFind(int n) {
    for (int i = 0; i < n; i++) {
        par.push_back(i);
        rank.push_back(0);
        cnt.push_back(1);
    }
}
int UnionFind::find(int x) {
    if (par[x] == x) return x;
    else return par[x] = find(par[x]);
}
void UnionFind::unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (rank[x] < rank[y]) {
        cnt[y] += cnt[x];
        par[x] = y;
    } else {
        cnt[x] += cnt[y];
        par[y] = x;
        if (rank[x] == rank[y]) rank[x]++;
    }
}
bool UnionFind::same(int x, int y) {
    return find(x) == find(y);
}
int UnionFind::count(int x) {
    return cnt[find(x)];
}
void UnionFind::printStatus() {
    printf("----------------\n");
    for (int i = 0; i < par.size(); i++) {
        printf("[node %d]: parent = %d, rank = %d, count = %d\n", i, par[i], rank[i], cnt[i]);
    }
}

int main() {
  
  int N, M;
  cin >> N >> M;

  UnionFind tree(N);
  rep(i,M) {
    int A, B;
    cin >> A >> B;
    A--; B--;
    tree.unite(A, B);
  }

  int ans = 0;
  rep(i,N) ans = max(ans, tree.count(i));

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 5856
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*);
    }
}

#[allow(unused_imports)]
use std::cmp::{min, max};

#[allow(unused_imports)]
use std::io::Write;
type I = usize;

fn main() {
    input!{
      n: usize,
      m: usize,
      c: i64,
      bs: [i64; m],
      aa: [[i64; m]; n]
    }

    let mut  ans = 0;
    for i in 0..n {
        let mut s = c;
        for j in 0..m {
            s += bs[j]*aa[i][j];
        }
        if s > 0 {
            ans += 1;
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
#include <iomanip>
#include <limits>
#include <fstream>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin>>N;
  int a[N];
  FOR(i,0,N)cin>>a[i];
  FOR(i,0,N){
    FOR(j,i+1,N){
      if(abs(a[i]-a[j])%(N-1)==0){
        cout<<a[i]<<" "<<a[j]<<endl;
        return 0;
      }
    }
  }
}


Measured memory_bytes: 3200
#include <bits/stdc++.h>
using namespace std;
long long  A[1000][1000];
int main()
{
    int N;
    cin>>N;
    long long  ans=0;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            cin>>A[i][j];
    for(int i=0;i<N;i++)
      for(int j=0;j<=i;j++){
        int biaozhi=1;
        for(int k=0;k<N;k++)
            if(A[i][j]>A[i][k]+A[k][j]){
                cout<<-1;
                return 0;
            }
            else if(i!=k&&j!=k&&A[i][j]==A[i][k]+A[k][j])
                biaozhi=0;
        if(biaozhi)
            ans+=A[i][j];
      }
    cout<<ans;
    return 0;
}

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

int main(){
    int n;
    cin >> n;
    vector<int> a(n + 1);
    rep(i, n) cin >> a[i];
    vector<int> b(n + 1);
    rep(i, n){
        b[a[i]] = i;
    }
    rep(i, n) cout << b[i] << " ";
    cout << endl;
    return 0;
}

Measured memory_bytes: 1664
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <list>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;

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

  vector<pair<int, int>> v(n);
  for (auto& row : v) cin >> row.first >> row.second;

  vector<vector<long long>> dp(n + 1, vector<long long>(w + 1, 0));
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= w; j++) {
      dp[i][j] = dp[i - 1][j];
      if (v[i - 1].first > j) continue;
      dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i - 1].first] + v[i - 1].second);
    }
  }
  cout << dp[n][w] << endl;

  return 0;
}


Measured memory_bytes: 80256
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;

int main()
{

    int a, b,c;
    scanf("%d%d%d",&a,&b,&c);
    if(b - a == c - b) printf("YES\n");
    else printf("NO\n");

	return 0;
}

Measured memory_bytes: 128
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;


int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(12);


    int n;
    cin >> n;

    long long res = 0;
    for (int i = 0, pre = -1; i < n; ++i) {
        int x;
        cin >> x;
        if (x < pre) {
            res += pre - x;
        }
        pre = max(pre, x);
    }

    cout << res << '\n';

    return 0;
}

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

int main(){
  int a,b;

  cin >> a >> b;

  if(a == 1 && b != 1)
    {
      cout << "Alice" << endl;
      return 0;
    }
  else if(a != 1 && b == 1)
    {
      cout << "Bob" << endl;
      return 0;
    }
  if(a >= b)
    {
      if(a == b)
	{
	  cout << "Draw" << endl;
	}
      else
	{
	  cout << "Alice" << endl;
	}
    }
  else
    {
      cout << "Bob" << endl;
    }
  return 0;
}


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

int main(int argc, char *argv[])
{
  int N, i, j;
  int *A;
  int tmp;
  int flag, ct = 0;

  scanf("%d", &N);

  A = (int *)malloc(sizeof(int) * N);

  for (i = 0; i < N; i++) scanf("%d", &A[i]);

  flag = 1;
  while (flag) {
    flag = 0;
    for (j = N - 1; j > 0; j--) {
      if (A[j] < A[j-1]) {
        tmp = A[j];
        A[j] = A[j-1];
        A[j-1] = tmp;
        ct++;
        flag = 1;
      }
    }
  }

  for (i = 0; i < N; i++) {
    if (i != N - 1) printf("%d ", A[i]);
    else printf("%d\n", A[i]);
  }
  printf("%d\n", ct);

  free(A);

  return 0;
}

Measured memory_bytes: 600
eval"N,*T="+`dd`.split*?,
M=10**9+7
z=1
N.times{|i|a=T[N+i]
t=T[i]
z=z*[[[a,t].min,0,t<=a ? 1:0],[0,0,0],[t>=a ? 1:0,0,t==a ? 1:0]][(T[N+i+1]||0)<=>a][T[i-1]*-2[i]<=>t]%M}
p z

Measured memory_bytes: 57676
def resolve():
    '''
    code here
    '''
    import math
    A, B, C, D = [int(item) for item in input().split()]

    if B//C == 0:
        num_C = 0
    elif B//C >= 1 and A % C == 0:
        num_C = B // C - A //C + 1
    elif B//C >= 1 and A % C != 0: 
        num_C = B // C - A //C
    else:
        num_C = B // C

    if B//D == 0:
        num_D = 0
    elif B//D >= 1 and A % D == 0:
        num_D = B // D - A //D + 1
    elif  B//D >= 1 and A % D != 0:
        num_D = B // D - A //D
    else:
        num_D = B // D

    lcm = C * D // math.gcd(C, D)
    if B//lcm == 0:
        num_CD = 0
    elif B//lcm > 1 and A  % lcm == 0:
        num_CD = B // lcm - A //lcm + 1
    elif B//lcm > 1 and A  % lcm != 0:
        num_CD = B // lcm - A //lcm
    else:
        num_CD = B // lcm

    # print(num_C, num_D, num_CD)
    print(B - A + 1 - (num_C + num_D - num_CD))


if __name__ == "__main__":
    resolve()


Measured memory_bytes: 9108
#include <bits/stdc++.h>
using namespace std;
template <typename Edge, typename T>
void Dijkstra(const vector<vector<Edge>> &edge, int s, vector<T> &d, T inf) {
    using P = pair<T, int>;
    priority_queue<P, vector<P>, greater<P>> q;
    for(int i = 0; i < edge.size(); i++) {
        d.push_back(inf);
    }
    d[s] = 0;
    q.push({0, s});
    while (q.size()) {
        T dist;
        int v;
        tie(dist, v) = q.top();
        q.pop();
        if (d[v] < dist) continue;
        for (auto &&e : edge[v]) {
            if (0 > d[e.to] || d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                q.push({d[e.to], e.to});
            }
        }
    }
}
struct Edge {
    int to;
    int64_t cost;
};
const int64_t INF = 1e16;
int main() {
    #ifdef DEBUG
    std::ifstream in("/home/share/inputf.in");
    std::cin.rdbuf(in.rdbuf());
    #endif
    int N;
    cin >> N;
    vector<vector<Edge>> E(N);
    for(int i = 0; i < N - 1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        E[a].push_back({b, c});
        E[b].push_back({a, c});
    }
    int Q, K;
    cin >> Q >> K;
    K--;
    vector<int64_t> D;
    Dijkstra<Edge, int64_t>(E, K, D, INF);
    for(int q = 0; q < Q; q++) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        cout << D[x] + D[y] << endl;
    }
    return 0;
}

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

#define all(x) x.begin(), x.end()

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MN = 1e5 + 5, LN = 17, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

int N;
ll t[1002], a[1002];

int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    cin >> N >> t[0] >> a[0];
    for (int i = 1; i < N; i++) {
        cin >> t[i] >> a[i];
        if (t[i] < t[i - 1] || a[i] < a[i - 1]) {
            ll mul = max((t[i]+t[i-1]-1)/t[i], (a[i]+a[i-1]-1)/a[i]);
            t[i] *= mul;
            a[i] *= mul;
        }
    }
    cout << t[N - 1] + a[N - 1] << '\n';
    return 0;
}

Measured memory_bytes: 256
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		Map<Integer,Boolean> ac = new LinkedHashMap<>();
		Map<Integer,Integer> wa = new LinkedHashMap<>();
		for(int i = 1; i <= n; i++) {
			ac.put(i,true);
			wa.put(i,0);
		}
		for(int i = 1; i <= m; i++) {
			int sub = sc.nextInt();
			String result = sc.next();
			if(result.equals("AC")) {
				ac.put(sub,false);
			}
			else {
				if(ac.get(sub)) {
					int temp = wa.get(sub)+1;
					wa.put(sub, temp);
				}
			}
		}
		int ac_result = 0;
		int wa_result = 0;
		for(int i = 1; i <= n; i++) {
			if(!ac.get(i)) {
				ac_result++;
				wa_result += wa.get(i);
			}
		}
		System.out.print(ac_result + " ");
		System.out.println(wa_result);
	}
}

Measured memory_bytes: 76496
n, m = map(int, input().split())
rootList = [-1 for i in range(n)]
 
def getRoot(x):
    if rootList[x] < 0:
        rootList[x] = x
    elif rootList[x] != x:
        rootList[x] = getRoot(rootList[x])
    return rootList[x]
 
 
def setSameRoot(x, y):
    x = getRoot(x)
    y = getRoot(y)
    rootList[x], rootList[y] = min(x, y), min(x, y)
 
for i in range(m):
    s, t = map(int, input().split())
    setSameRoot(s, t)
q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    print("yes" if getRoot(s) == getRoot(t) != -1 else "no")

Measured memory_bytes: 7016
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <sstream>

#define ll long long int
#define rep(i,x,y) for(int i=x;i<y;i++)
#define rel(i,x,y) for(int i=x-1;i>=y;i--)
#define all(x) x.begin(),x.end()
#define NMAX 100
#define WMAX 10000
using namespace std;
int dp[NMAX+1][WMAX+1] = {};

int main(){
	int N,W;
	cin >> N >> W;
	int v[N+1],w[N+1];
	v[0] = 0;w[0]=0;
	rep(i,1,N+1){
		cin >> v[i] >> w[i];
	}
	
	rep(i,1,N+1){
		rep(j,1,W+1){
			dp[i][j] = max(dp[i-1][j],dp[i][j]);
			if(j>=w[i]){
				dp[i][j] = max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
			}
		}
	}
	
	cout << dp[N][W] << endl;
}



Measured memory_bytes: 7024
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<cstring>
#include<math.h>
#include<map>
#include<bitset>
#include<iomanip>
#include<queue>
#include<functional>
#include<stack>
#include<tuple>
#include<cassert>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
using P = pair<int, int>;

int main() {
  long long N, A, B;
  cin >> N >> A >> B;
  long long a = N / (A + B);
  long long b = N % (A + B);
  long long ans = A * a;
  long long plus;
  plus = min(A, b);
  ans += plus;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

int main() {
	int n; scanf("%d", &n); std::vector<int> p(n);
	for(int i = 0; i < n; i++) scanf("%d", &p[i]);

	int ans = 1 << 30;
	for(int loop = 0; loop < 2; loop++) {
		std::vector<int> dp(n + 1, 0);
		for(int i = 0; i < n; i++) {
			int val = p[i];

			dp[val] = dp[val - 1] + 1;
		}
		for(auto v: dp) ans = std::min(ans, n - v);

		reverse(begin(p), end(p));
		for(auto& v: p) v = n - v + 1;
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 1792
/*
      THINK  TWICE  CODE  ONCE
        KEEP   GOING   BI*CH
           NEVER GIVE UP
               3 R B
                . .
                 .
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define bp  __builtin_popcount
#define pb push_back
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> indexed_set;
const int maxn=1e5+5;
const  double EPS = 1e-14;
const ll MOD = 1e9+7;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    while(true)
    {
        c -= b;
        if(c<=0)
            return cout<<"Yes",0;
        a -= d;
        if(a<=0)
            return cout<<"No",0;
        else
            continue;
    }
}


Measured memory_bytes: 3568
// --------------------<optimizations>--------------------
#pragma GCC optimize("O3")
//(UNCOMMENT WHEN HAVING LOTS OF RECURSIONS)\
#pragma comment(linker, "/stack:200000000")
//(UNCOMMENT WHEN TRYING TO BRUTEFORCE WITH A LOT OF LOOPS)\
#pragma GCC optimize("unroll-loops")

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair<ll,ll>
#define vpii vector<pair<ll,ll> >
#define F first
#define S second
#define ld long double
#define built __builtin_popcountll
#define mst(a,i) memset(a,i,sizeof(a))
#define all(x) x.begin(),x.end()
#define itit(it,a) for(auto it=(a).begin(); it!=(a).end(); it++)
#define rep(i,a,b) for(ll i=a; i<b; i++)
#define repr(i,a,b) for(ll i=a; i>b; i--)
#define reprr(i,a,b) for(ll i=a; i>=b; i--)
#define pi 3.14159265358979323846264338327950288419716939937510582097494459230
ll max3(ll x,ll y,ll z) {return max(max(x,y),z);}
ll min3(ll x,ll y,ll z) {return min(min(x,y),z);}
const ll M=2e5+10,M2=1e6+10,mod=1e9+7,inf=1e17+10;
const int INF=1e9+7;
void add(int& a, int b) {a+=b;if(a>=mod){a-=mod;}}
#define trace1(x)                    cerr<<#x<<": "<<x<<endl
#define trace2(x, y)                 cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)                 cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)             cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)         cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f)     cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
int X[] = {0, 1, 0, -1};
int Y[] = {-1, 0, 1, 0};
ll power(ll x,ll n){ll result=1;while(n>0){if(n%2==1)result=(result*x)%mod; x=((x%mod)*(x%mod))%mod;n=n/2;}return result;}



int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll a,b;
    cin >> a >> b;
    if(a>=1 && a<=9 && b>=1 && b<=9) cout << a*b;
    else cout << -1;
    return 0;
}
/* The judge is never wrong! Your code is buggy
   Look for:
 * * Read the problem carefully.
 * * Don't forget to sort(), mod, ll!!!!
 * * Initial value = +/- infinity instead of zero!!!
 * * an easier and alternate approach
 * * read the problem statement carefully
 * * if concept is correct and still WA, try with a different implementation
 * * special cases (n=1?)
 * * if you have no idea just guess the appropriate well-known algorithm instead of doing nothing :/
 */


Measured memory_bytes: 256
/*input
6
30 10 60 10 60 50
*/

#include<bits/stdc++.h>
#define printarr(a,n) for(int i=0;i<n;i++) {cout << a[i] << " ";} cout << "\n"
#define getarr(a,n) for(int i=0;i<n;i++) cin >> a[i]
#define deb2d(a,n,m) for(int i=0;i<n;i++){for(int j=0;j<m;j++) cout << setw(3) << a[i][j] << " "; cout << "\n";} cout << "\n\n";cin.ignore();
#define deb(x) cout << x << " ";
#define pb(x) push_back(x)
#define vi vector<int>
#define pii pair<int,int>
#define int long long int
#define endl "\n"
#define MOD 1000000007
#define bak cout << "Blah\n"
using namespace std;

void executor(int test_case){
	int n,k;
	cin >> n;
	vi a(n); getarr(a,n);
	vi dp(n);
	dp[1] = abs(a[1] - a[0]);
	for(int i = 2; i < n; ++i){
		int peeche_wala = dp[i-1] + abs(a[i] - a[i-1]);
		int peeche_ke_peeche_wala = dp[i-2] + abs(a[i] - a[i-2]);
		dp[i] = min(peeche_wala, peeche_ke_peeche_wala);
	}
	//printarr(dp,n);
	cout << dp[n-1] << endl;
}

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t = 1;
	//cin >> t;
	for(int i = 1 ; i <= t ; i++) executor(i);
}

Measured memory_bytes: 4740
A = []
B = []
C = []
for i in range(5):
    A.append(int(input()))
    if A[i]%10 == 0:
        B.append(A[i])
    else:
        B.append((A[i]-A[i]%10)+10)
    C.append(B[i]-A[i])
sb = sum(B)
ans = sb
for i in range(5):
    ans = min(ans,sb-C[i])
print(ans)

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

using namespace std;

template <typename T> T gcd(T x, T y) {
  if (y == 0)
    return x;
  return gcd(y, x % y);
}

template <typename T> T lcm(T x, T y) {
  if (x == 0 || y == 0)
    return 0;
  return x / gcd(x, y) * y;
}

int main() {
  int N;
  cin >> N;
  int cnt = 0;
  int cnt2 = 0;
  for (int i = 0; i < N; i++) {
    int a;
    cin >> a;
    if (a % 4 == 0)
      cnt++;
    else if (a % 2 == 0)
      cnt2++;
  }
  if (cnt2 > 1)
    N -= (cnt2 - 1);

  cout << (cnt >= (N / 2) ? "Yes" : "No") << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repe(i, n) for (int i = 0; i <= (int)(n); i++)
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define ANS cout << ans << endl
#define all(a) a.begin(),a.end()
#define SORT(a) sort(all(a))
#define REVERSE(a) reverse(all(a))
#define int ll
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORe(i, m, n) for(int i = m;i <= n;i++)
#define VIin(a) for(int i=0; i<a.size(); i++) cin >> a[i]
#define OUT(a) cout << a << endl
#define IN(a) cin >> a
#define INT(a) int a; cin >> a
typedef vector<int> VI;
typedef vector<VI> VVI;
const int MOD=1e9+7;
const long long INF = 1LL << 60;
/*最大公約数*/int gcd(int x, int y) { return y ? gcd(y,x%y) : x;}
/*最小公倍数*/int lcm(int a, int b) { int g = gcd(a, b); return a / g * b; }
/*素数判定*/int isPrime(int n){if(n<2){return 0;}for(int i=2; i*i<=n; i++){if(n%i==0){return 0;}}return 1;}
/*約数列挙*/vector<int> getDivisor(int n){vector<int> v; for(int i=1; i*i<=n; i++){if(n%i==0){v.push_back(i);if(i!=n/i){v.push_back(n/i);}}}sort(v.begin(),v.end()); return v;}
//----------------------------------------------
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    INT(x);
    int a,b; cin >> a >> b;
    OUT((x-a) % b);

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <vector>
#include <string.h>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <deque>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <stdio.h>

using namespace std;

#define fo(i,n) for(int i=0; i<(int)n; i++)
#define rep(it,s) for(__typeof((s).begin()) it=(s).begin();it!=(s).end();it++)
#define mp(a,b) make_pair(a,b)
#define pb(x) push_back(x)
#define pii pair<int,int>

int w,n;
int v[50100];
int f[50100];

bool check(int x) {
    for(int i=0; i<=n+1; i++) f[i] = 0;
    int l = 1, r = 1;
    int suml = v[0], sumr = v[0];
    f[0] = 1;
    f[1] = -1;

    for (int i=0; i<n; i++) {
        f[i+1] += f[i];
        if (f[i]>0) {
            while (l<n && suml<=w) {
                suml += 1 + v[l];
                l++;
            }
            while (r<n && sumr<w) {
                sumr += x + v[r];
                r++;
            }
            f[l]--;
            f[r]++;
            if (l==n && suml<=w) f[n]++;
        }
        suml -= 1+v[i];
        sumr -= x+v[i];
    }
    return f[n]>0;
}

int main() {

    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);

    while (cin>>w>>n && w!=0) {
        for (int i=0; i<n; i++) scanf("%d",v+i);

        int lo = 1;
        int hi = w;
        while (lo<hi) {
            int mi = (lo+hi)/2;
            if (check(mi)) hi = mi;
            else lo = mi+1;
        }

        cout<<lo<<"\n";
    }

    return 0;

}

Measured memory_bytes: 1636
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<fstream>

#define MOD (1000000007)

using namespace std;

typedef long long int Int;

constexpr Int TEN(int n) { return n == 0 ? 1 : 10 * TEN(n-1); }

Int N,K;
vector<Int> A;
Int sum;

int main(void) {
    cin>>N>>K;

    for(int i = 0;i < N;i++) {
        Int a;
        cin>>a;
        A.push_back(a);
        sum += a;
    }

    Int ans = 1;
    set<Int> D;
    for(int i = 1;i*i <= sum;i++) {
        if(sum % i == 0) {
            D.insert(i);
            D.insert(sum/i);
        }
    }

    for(auto u:D) {
        vector<int> a(N);
        for(int i = 0;i < N;i++) {
            a[i] = A[i] % u;
        }
        sort(a.begin(),a.end());
        Int left = 0;
        Int right = 0;
        for(int i = 0;i < N;i++) {
            right += u - a[i];
        }

        Int need = TEN(18);
        for(int i = 0;i < N;i++) {
            left += a[i];
            right -= u-a[i];
            need = min(need,max(left,right));
        }
        if(need <= K)
            ans = max(ans,u);
    }

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



Measured memory_bytes: 256
n, m = map(int, input().split())
k = sorted(list(map(int, input().split())))

if n >= m:
    print(0)
    exit()
dis = []
for i in range(m-1):
    dis.append(k[i+1] - k[i])

dis.sort()
dis.reverse()
sub = 0
#print(dis)
for i in range(n-1):
    sub += dis[i]
    
print(sum(dis) - sub)

Measured memory_bytes: 13968
#include<stdio.h>
#define max(a,b) ((a>b?a:b))
int main(){
  int K,N,A0,An,An_old;
  int i, max_delA;
  scanf("%d%d",&K,&N);
  max_delA = 0;
  scanf("%d",&An);
  A0 = An;
  An_old = An;
  for(i=1;i<N;i++){
    scanf("%d",&An);
    max_delA = max(max_delA, An - An_old);
    An_old = An;
  }
  max_delA = max(max_delA, K + A0 - An);
  printf("%d",K-max_delA);
}

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

int main()
{


	string s;
	cin >> s;
	int n = s.length();
	if (n == 1 && s[0] == '0')
		cout << "Yes";
	else {
		int sum = 0;
		for (int i = 0; i < n; i++)
		{
			sum += (s[i] - '0');
		}
		if (sum % 9 == 0)
			cout << "Yes";
		else
			cout << "No";
	}
	cout << endl;
}



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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl




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




ll f(ll b, ll n) {
    if (n<b) return n;
    return f(b,n/b) + n%b;
}
     
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    ll n,s; cin>>n>>s;

    for (ll b=2; b*b<=n; b++) {
	if (f(b,n) == s) out(b);
	//cout<<b<<": "<<f(b, n)<<endl;
    }


    ll x = n-s;

    if (x<0) out(-1);

    if (x==0) {
	assert(n==s);
	out(n+1);
    }


    set<ll> res;

    for (ll i=1; i*i<=x; i++) {
	if (x%i == 0) {
	    if (f(i+1,n)==s) res.insert(i + 1);
	    if (f(x/i + 1,n)==s) res.insert(x/i + 1);
	}
    }

    if (res.empty()) out(-1);

    out(*res.begin());
    return 0;
}


Measured memory_bytes: 256
fun main(args: Array<String>) {
    val n = readLine()!!.toLong()

    if ( n == 0L){
        println('0')
    }

    // 下から桁を決定していく，それまでに決まった桁の値がわかれば現在の桁も決定できる
    // 1桁目が 2 で割ったあまりに影響, 2桁目が 4 で割ったあまりに影響・・・
    var sum = 0L
    var denom = 1L
    var now = 1L
    var i = 0
    var ans = ""
    while (sum != n) {

        denom *= 2

        if ( (n-sum) % denom != 0L) {
            // n が 2^(i+1) で割り切れない( 2^(i) を使っている) =>  i は 1
            ans = "1" + ans
            sum += Math.pow(-1.0, i.toDouble()).toInt() * now
        } else {
            // n が 2^(i+1) で割り切れる i は 0
            ans = "0" + ans
        }

        i+=1
        now *= 2
    }

    println(ans)
}

Measured memory_bytes: 31660
#include<stdio.h>

int main(){
	int n;
	scanf("%d", &n);
	
	int ratusan = 0, puluhan = 0, satuan= 0;
	
	ratusan = n / 100;
	puluhan = (n / 10) - (ratusan * 10); //misal n = 271, 271 - 2
	satuan = n % 10;
	
	if(ratusan == 7 || puluhan == 7 || satuan == 7){
		printf("Yes\n");
	}
	else{
		printf("No\n");
	}
	return 0;
}

Measured memory_bytes: 1648