akhauriyash/Code-Regression huggingface dataset:
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
#define dec(n) cout << fixed << setprecision(n);
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;

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

ll mod(ll a){
  return (a % 1000000007);
}

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


int main(){
  ll l,r; cin >> l >> r; ll ans = 2018;
  
  if(r-l <= 2019){
    for(ll i=l; i <= r; i++){
      for(ll j=l; j <= r; j++){
       
        if(i != j){
          ans = min(ans,(i*j) % 2019);
        }
      }
    }
  }
  
  else{
    for(ll i=l; i <= l+2019; i++){
      for(ll j=l; j <= l+2019; j++){
        
        if(i != j){
          ans = min(ans,(i*j) % 2019);
        }
      }
    }
  }
  
  cout << ans << endl;
  
}
  
  

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <string>
//#include <queue>
using namespace std;
#define ll long long
#define ld long double


int arrt[101]={0};



int main()
{
    //ifstream fi;
    //ofstream fo;
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin >> n >> m;
    int res=((n+1)*n);
    res/=2;
    res+=(m-1)*n;
    int sum=1000000;
    int s2=0;
    for(int i=1;i<=n;i++)
    if (abs(m+i-1)<sum)
    {
        sum=abs(m+i-1);
        s2=m+i-1;
    }
    cout << res-s2;
    return(0);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    int n, a = 0, c = 0;
    string s;
    cin >> n >> s;
    for (int i = 0; i < n; i++) {
        if (s[i] == '(') c++;
        else c--;
        if (c < 0) a++, c = 0;
    }
    while (a--) cout << '(';
    cout << s;
    while (c--) cout << ')';
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mkp make_pair
#define SZ(x) ((int)(x).size())
#define MEM(x,a) memset(x,a,sizeof(x))
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> VI;
typedef vector<ll> VL;
const ll mod=1000000007,N=1e5+5,M=1e5+5,INF=0x3f3f3f3f;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
//head

int main(void){
    int n;
    cin>>n;
    bool flag=0;
    while(n){
        if(n%10==7)flag=1;
        n/=10;
    }
    cout<<(flag?"Yes":"No");
    return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <iomanip>
#include <string>
#include <map>
#include <math.h>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <set>
#include <queue>
#include <sstream>
#include <stack>
#include <deque>
#include <memory.h>
#include <cassert>
#include <ctime>
#include <climits>
#include <list>
#include <time.h>
#include <unordered_map>
#include <bitset>
#include <exception>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned long long ull;
#define pb push_back
#define mp make_pair
#define FILE "file"
#define lc v << 1
#define rc (v << 1) + 1
#define inf 1e+9
#define linf ll(1e+18)
#define dinf 1e+14

typedef long long ll;
#define pb push_back
#define mp make_pair

vector<int> a, b, c;

int f(vector<int> &v, int l, int r, int x)
{
    if(l > r)
    {
        return 0;
    }
    
    int m = (l + r) >> 1;
    if(v[m - 1] < x)
    {
        return m - l + 1 + f(v, m + 1, r, x);
    }
    return f(v, l, m - 1, x);
}

int g(vector<int> &v, int l, int r, int x)
{
    if(l > r)
    {
        return 0;
    }
    
    int m = (l + r) >> 1;
    if(v[m - 1] > x)
    {
        return r - m + 1 + g(v, l, m - 1, x);
    }
    return g(v, m + 1, r, x);
}

void solve()
{
    int n;
    cin >> n;
    a.resize(n);
    b.resize(n);
    c.resize(n);
    
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    
    for(int i = 0; i < n; i++)
    {
        cin >> b[i];
    }
    
    for(int i = 0; i < n; i++)
    {
        cin >> c[i];
    }
    
    sort(a.begin(), a.end());
    sort(c.begin(), c.end());
    
    ll res = 0;
    for(int i = 0; i < n; i++)
    {
        int x = f(a, 1, n, b[i]);
        int y = g(c, 1, n, b[i]);
        res += x * 1ll * y;
    }
    cout << res;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0), cout.tie(0);
    //freopen(FILE ".in", "r", stdin);freopen(FILE ".out", "w", stdout);
    //freopen("file.in", "r", stdin);freopen("file.out", "w", stdout);
    int t = 1;
    //cin >> t;
    
    while(t--)
    {
        solve();
    }
    
    return 0;
}


Measured memory_bytes: 1408
using System;
using System.Diagnostics;
using System.IO;
using System.Text;
using System.Linq;
using System.Collections.Generic;
using System.Text.RegularExpressions;

class Program
{
    const string Yes = "Yes";
    const string No = "No";
    const long Mod = 1000000007;

    static void Main(string[] args) {
#if DEBUG
        MyDebugger.Test(process, "../TextFile1.txt");
#else
        object ret = process(new StreamReader(Console.OpenStandardInput()));
        Console.WriteLine(ret);
#endif
    }

    static object process(TextReader input) {
        var spl = input.ReadLine().Split(' ');
        var n = int.Parse(spl[0]);
        var m = int.Parse(spl[1]);
        var x = int.Parse(spl[2]);
        var ary = ToIntArray(input.ReadLine(), m);

        int left = 0;
        int right = 0;

        foreach(int i in ary) {
            if (i < x) left++;
            if (i > x) right++;
        }

        return Math.Min(left, right);
    }

    static int[] ToIntArray(string strs, int n) {
        var ret = new int[n];
        var spl = strs.Split(' ');
        for (int i = 0; i < n; i++)
            ret[i] = int.Parse(spl[i]);
        return ret;
    }
}


Measured memory_bytes: 13140
#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std ;

int n, cnt[1000008]; 
bool prime[1000008];

int main() {
	prime[1] = true;
	for (int i = 2; i <= 999999; i ++) prime[i] = false;
	for (int i = 2; i <= 999999; i ++) {
		if (!prime[i]) {
			for (int j = 2*i; j <= 999999; j += i) {
				prime[j] = true;
			}
		}
	}
	cnt[1] = 0;
	for (int i = 2; i <= 999999; i ++) {
		cnt[i] = cnt[i - 1] + (int)(!prime[i]);
	}
	while (cin >> n) {
		cout << cnt[n] << endl ;
	}
	return 0 ;
}


Measured memory_bytes: 7864
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define endl '\n'
#define pi pair<int, int>
#define f first
#define s second

long long n;
vector<int> v;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	
	long long ret = 1, x = n - 1;
	for(long long i = 2; i * i <= n; i++){
		int c;
		for(c = 1; x % i == 0; x /= i) c++;
		ret *= c;
		
		if(n % i == 0){
			v.push_back(i);
			if(i * i != n) v.push_back(n / i);
		}
	}
	ret *= (x > 1) + 1;
	
	for(long long i : v){
		x = n;
		while(x % i == 0) x /= i;
		ret += x % i == 1;
	}
	
	cout << ret << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <limits>
#include <numeric>
#include <algorithm>
#include <functional>

#include <vector>

using namespace std;

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

	int N, K;
	cin >> N >> K;

	vector<int> P(N, 0);

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

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

	int result = 0;
	for (int i = 0; i < K; i++)
	{
		result += P[i];
	}

	cout << result;
	
	return 0;
}


Measured memory_bytes: 3668
fun main(args: Array<String>) {
    val N = nextInt()
    val A = Array(N) { nextInt() }
    val B = A.sortedDescending()
    A.forEach {
        val ans = if (it == B[0]) B[1] else B[0]
        println(ans)
    }
}
fun next() = readLine()!!
fun nextInt() = Integer.parseInt(next())

Measured memory_bytes: 58084
def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def count_attack(H):
    if H == 1:
        return 1
    return 2*count_attack(H//2)+1


def solve():
    H = read_int()
    return count_attack(H)


if __name__ == '__main__':
    print(solve())


Measured memory_bytes: 62016
#include<bits/stdc++.h>
#define int long long
#define FLASH cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
#define FILEIO freopen("/home/aman/Desktop/Kachda/input.txt", "r", stdin); //freopen("/home/aman/Desktop/Kachda/output.txt", "w", stdout);
using namespace std;

int n, m;

signed main()
{
   
    FLASH

    cin>>n>>m;

    set <int> s;
    int l = 1, r = n;
    for(int i = 1; i <= m; i++){
        if(s.count(r - l) or s.count(n - r + l) or (r - l == n/2 and ((n&1) == 0)))
            l++;
        cout<<l<<" "<<r<<'\n';
      
      	assert(l < r);
        s.insert(r - l);
        s.insert(n - r + l);
        l++, r--;
    }
}

Measured memory_bytes: 12056
#include <iostream>
#include <string>

int main(void){

  int n, a, b;

  std::cin >> n >> a >> b;

  int c = b-a;
  if(c%2){
    std::cout << "Borys" << std::endl;
  }else{
    std::cout << "Alice" << std::endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <cmath>
#include <set>
#include <bitset>
#include <limits>
#include <queue>

using namespace std;

#define ll long long

int main(void){
    int n, m;
    cin >> n >> m;
    vector<int> a(m), b(m);
    for(int i = 0;i < m;++i){
        int tmpa, tmpb;
        cin >> tmpa >> tmpb;
        a[i] = tmpa -1;
        b[i] = tmpb-1;
    }

    vector<int> dist(n, 1000000000);

    vector<vector<int>> coef(n);
    for(int i = 0;i < m;++i){
        coef[a[i]].push_back(b[i]);
        coef[b[i]].push_back(a[i]);
    }

    // for(int i = 0;i < n;++i){
    //     cout << coef[i].size() << endl;
    // }

    queue<int> next;
    next.push(0);
    dist[0] = 0;
    vector<int> ans(n);
    for(int i = next.front();next.size() > 0; i = next.front()){
        // cout << i << endl;
        for(int j = 0;j < coef[i].size();++j){
            if(dist[coef[i][j]] > dist[i]+1){
                dist[coef[i][j]] = dist[i]+1;
                // cout << "next push : " << coef[i][j] << endl;
                next.push(coef[i][j]);
                ans[coef[i][j]] = i;
            }
        }
        next.pop();
        // cout << "next is : " << next.front() << endl;
    }

    int flag = 1;
    for(int i = 1;i < n;++i){
        if(dist[i] == 1000000000){
            flag = 0;
        }
    }

    if(flag){
        cout << "Yes" << endl;
        for(int i = 1;i < n;++i){
            cout << ans[i]+1 << endl;
        }
    }else{
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 12068
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int N = 2e5;
int Sa[N];
int Sc[N];
int main(){
    int n,q;
    string s;
    while(cin>>n>>q>>s){
        Sa[0]=Sc[0] = 0;
        Sa[1]=Sc[1] = 0;
        for(int j=1 ;j<(int)s.size(); j++){
            char c = s[j];
            char bc = s[j-1];
            int i = j + 1;
            if(bc == 'A'&& c == 'C'){
                Sa[i] = Sa[i-1]+1;
            }
            else {
                Sa[i] = Sa[i-1];
            }
        }
        for(int j = 2 ;j<=(int)s.size(); j++){
            //cout<<j<<" "<<Sa[j]<<endl;
        }
        while(q--){
            int l,r;cin>>l>>r;
            int ans = Sa[r] - Sa[l-1];
            l --;
            if(l >=1){
                if(s[l] == 'C'&& s[l-1] == 'A'){
                    ans --;
                }
            }
            if(r - l + 1<=1){
                cout<<0<<endl;
            }
            else {
                cout<<ans<<endl;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 1408
# -*- coding: utf-8 -*-
H, W = map(int, input().split())
map = [list(input()) for i in range(H)]
cost_map =  [[None]*W for i in range(H)]
whites = 0
for i in range(H):
    for j in range(W):
        if map[i][j]==".":
            whites += 1
# 迷路を最短で抜ける
queue = list()
queue.append([0, 0])
cost_map[0][0] = 0
while queue:
    x,y = queue.pop(0)
    if x==H-1 and y==W-1:break
    current = cost_map[x][y]
    if 0<=x+1<H:
        if cost_map[x+1][y] is None and map[x+1][y]==".":
            queue.append([x+1, y])
            cost_map[x+1][y] = current + 1
    if 0<=x-1<H:
        if cost_map[x-1][y] is None and map[x-1][y]==".":
            queue.append([x-1, y])
            cost_map[x-1][y] = current + 1
    if 0<=y+1<W:
        if cost_map[x][y+1] is None and map[x][y+1]==".":
            queue.append([x, y+1])
            cost_map[x][y+1] = current + 1
    if 0<=y-1<W:
        if cost_map[x][y-1] is None and map[x][y-1]==".":
            queue.append([x, y-1])
            cost_map[x][y-1] = current + 1
# ゲーム開始時の白のマスの数から最短のマス目を引く
if cost_map[H-1][W-1] is None:
    print("-1")
else:
    print(whites - cost_map[H-1][W-1]-1)


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

//typedef
//------------------------------------------
typedef long long LL;
typedef vector<LL> VL;
typedef vector<VL> VVL;
typedef vector<string> VS;
typedef pair<LL, LL> PLL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).rbegin(),(c).rend())

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int MOD = 1000000007;

// grid
//--------------------------------------------
VL dx = {0, 1, 0, -1};
VL dy = {1, 0, -1, 0};
VL dx2 = {-1, 0, 1, -1, 1, -1, 0, 1};
VL dy2 = {-1, -1, -1, 0, 0, 1, 1, 1};

//debug
//--------------------------------------------
#define dump(x)  cerr << #x << " = " << (x) << endl
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl

//IO accelerate
//--------------------------------------------
struct InitIO {
    InitIO() {
        cin.tie(nullptr);
        ios_base::sync_with_stdio(false);
        cout << fixed << setprecision(30);
    }
} init_io;

//template
//--------------------------------------------
template<typename T>
istream& operator >>(istream& is, vector<T>& vec) {
  for(T& x: vec) is >> x;
  return is;
}
template<typename T>
ostream& operator <<(ostream& os, const vector<T>& vec) {
  for(int i=0; i<vec.size(); i++){
    os << vec[i] << ( i+1 == vec.size() ? "" : "\t" );
  }
  return os;
}
template<typename T>
ostream& operator <<(ostream& s, const vector<vector<T>>& vv) {
	for (int i = 0; i < vv.size(); ++i) {
		s << vv[i] << endl;
	}
	return s;
}
template<typename T>
ostream& operator <<(ostream& s, const vector<pair<T, T>>& vp) {
	for (int i = 0; i < vp.size(); ++i) {
		s << "(" << vp[i].first << "," << vp[i].second << ")" << ( i+1 == vp.size() ? "" : ",\t" );
	}
	return s;
}

// 多重vector
// auto dp=make_v<int>(4,h,w) みたいに使える
template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

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

// 多重vectorのためのfill
// fill_v(dp,0) みたいに使える
template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}

//main code

int main(int argc, char const* argv[])
{
	int x;
	cin >> x;
	int d = x/100;
	if (d*105 >= x) {
		cout << 1 << endl;
	} else {
		cout << 0 << endl;
	}
	return 0;
}


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

using namespace std;

using ll = long long;
using vi = vector<int>;

const ll linf = 1LL << 62;
const int inf = 999999;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
const ll atcoder = int(1e9 + 7);

#define Endl endl
#define pr(x) cout << x << endl
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)
#define all(x) x.begin(),x.end()
#define atcoder(int)1e9+7
#define rep(i,n) for(int i = 0;i<n;i++)
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)


ll gcd(ll a, ll b) {//最大公約数
	if (a%b == 0)return b;
	else gcd(b, a%b);
}

ll lcm(ll a, ll b) {//最小公倍数
	return (a / gcd(a, b))*b;
}

ll t[100010];

int  main() {
	
	int n, c, k;
	cin >> n >> c >> k;
	rep(i, n)cin >> t[i];
	sort(t, t + n);
	int ans = 0;

	rep(i, n) {
		int a = t[i];
		i++;
		ans++;
		if (i > n)break;
		for(int j = 0;j<c-1;j++){
			if (i > n)break;
			if (t[i] <= a + k)i++;
			else break;
		}
		i--;
	}

	pr(ans);
	return 0;

}

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

int main(void) {
    int n;
    cin >> n;
    int d[n];
    for(int i = 0; i < n; i++) {
        cin >> d[i];
    }

    int sum = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            sum += d[i] * d[j];
        }
    }

    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
	long long a,b,i,ans=1;
	cin>>a>>b;
	for(i=a;i<=b;i++) ans*=i;
	if(a>0) cout<<"Positive"<<endl;
	if(a<=0&&b>=0) cout<<"Zero"<<endl;
	if(a<0&&b<0){
		a=-a;b=-b;
		if((a-b)%2==0) cout<<"Negative"<<endl;
		else cout<<"Positive"<<endl;
	}
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

const (
	A = 65
	Z = 90
)

func main() {
	var N int
	var S string

	fmt.Scanf("%d\n%s\n", &N, &S)
	for _, rs := range []rune(S) {
		if int(rs)+N > Z {
			fmt.Print(string([]rune{rs + int32(N-Z+A-1)}))
		} else {
			fmt.Print(string([]rune{rs + int32(N)}))
		}
	}
	fmt.Println()
}


Measured memory_bytes: 896
#include<bits/stdc++.h>
using namespace std;
int n,k,s;
int main()
{
    scanf("%d%d%d",&n,&k,&s);
    for(int i=1;i<=k;i++)printf("%d ",s);
    if(s<1000000000)
    {
        for(int i=k+1;i<=n;i++)printf("1000000000 ");
    }
    else for(int i=k+1;i<=n;i++)printf("1 ");
    putchar(10);
    return 0;
}

Measured memory_bytes: 1280
#include<iostream>
using namespace std;
int main(){
    
    int a;
    int b;
    int c;
    cin >> a >> b >> c;
    
    if (a <= b) {
        
        if (b <= c) {
            
            cout << a << " " << b << " " << c << endl;
            
        } else if (a <= c){
            
            cout << a << " " << c << " " << b << endl;
            
        } else {
            
            cout << c << " " << a << " " << c << endl;
            
        }
        
    } else if (b <= c) {
        
        if (a <= c) {
            
            cout << b << " " << a << " " << c << endl;
            
        } else {
            
            cout << b << " " << c << " " << a << endl;
            
        }
        
    } else {
        
        cout << c << " " << b << " " << a << endl;
        
    }
        
    }


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

vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}

const int MAX = 210000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];
void COMinit(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < MAX; i++){
        fac[i] = fac[i-1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
        finv[i] = finv[i-1] * inv[i] % MOD;
    }
}
long long COM(int n, int k){
    if(n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD;
}

int main() {
    int N, M;
    COMinit();
    cin >> N >> M;
    auto vec = prime_factorize(M);
    long long res = 1;
    for (auto pa : vec) {
        int num = pa.second;
        long long tmp = COM(num+N-1, N-1);
        res = (res * tmp) % MOD;
    }
    cout << res << endl;
}     

Measured memory_bytes: 5120
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i++)
#define show(x) {for(auto i: x){cout << i << " ";} cout<<endl;}
#define showm(m) {for(auto i: m){cout << m.x << " ";} cout<<endl;}
typedef long long ll;
typedef pair<int, int> P;
ll gcd(int x, int y){ return y?gcd(y, x%y):x;}
ll lcm(ll x, ll y){ return (x*y)/gcd(x,y);}


int main()
{
    string s;
    cin >> s;
    vector<bool> e(4);
    rep(i, s.size()){
        if (s[i] == 'N') e[0] = true;
        else if (s[i] == 'S') e[1] = true;
        else if (s[i] == 'E') e[2] = true;
        else e[3] = true;
    }

    if (e[0]^e[1] || e[2]^e[3]) cout << "No" << endl;
    else cout << "Yes" << endl;

}


Measured memory_bytes: 256
s = input()

if s[0] != "A":
    print("WA")
    exit()

if s[1].isupper() or s[-1].isupper():
    print("WA")
    exit()

count = 0
for s_ in s[2:]:
    if s_.isupper():
        if s_ == "C":
            count += 1
        else:
            print("WA")
            exit()
        

if count == 1:
    print("AC")
else:
    print("WA")

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

int ct[55];
int main()
{
    int n, m;
    scanf("%d %d",&n,&m);
    for (int i = 0; i<m; i++)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        ct[a]++;
        ct[b]++;
    }
    for (int i = 1; i<=n; i++)
    {
        printf("%d\n",ct[i]);
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define EPS (1e-10)
#define rep(i,n)for(ll i=0;i<n;i++)
using namespace std;
typedef long long ll;
typedef pair<int, int>P;

char s[200][200];
int main() {
	int n, m, d; cin >> n >> m >> d;
	rep(i, n)cin >> s[i];
	int cnt = 0;
	rep(i, n) {
		for (int j = 0; j <= m - d; j++) {
			bool ok = true;
			rep(k, d) {
				if (s[i][j + k] == '#')ok = false;
			}
			if (ok)cnt++;
		}
	}
	rep(i, m) {
		for (int j = 0; j <= n - d; j++) {
			bool ok = true;
			rep(k, d) {
				if (s[j + k][i] == '#')ok = false;
			}
			if (ok)cnt++;
		}
	}
	cout << cnt << endl;
}

Measured memory_bytes: 3100
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e12;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s, t;
    cin >> s >> t;
    vector<string> ans; 
    rep(i, 0, s.size() - t.size() + 1){
        string u = s;
        bool f = true;
        rep(j, 0, t.size()){
            if(u[i + j] == t[j]) continue;
            else if(u[i + j] == '?'){
                u[i + j] = t[j];
            }else{
                f = false;
            }
        }
        if(f){
            rep(j, 0, u.size()){
                if(u[j] == '?') u[j] = 'a';
            }
            ans.push_back(u);
        }
    }
    sort(all(ans));
    if(ans.size() == 0){
        cout << "UNRESTORABLE" << endl;
    }else{
        cout << ans[0] << endl;
    }
}

Measured memory_bytes: 256
n = int(input())
al = []
for _ in range(n):
    a = int(input())
    al.append(a)

al = sorted(al)
ans = 0

before = 0
for a in al:
    if before == a:
        ans -= 1
        before = 0
    else:
        ans += 1
        before = a
    
print(ans)


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

int main() {
 int a, b, c, d;
  cin >> a >> b >> c >> d;
  if ((a+b)>(c+d)) {
    cout << "Left" << endl;
  }
  else if ((a+b)<(c+d)){
    cout << "Right" << endl;
  }
  else {
    cout << "Balanced" << endl;
  }
 
    
 return 0;
}


Measured memory_bytes: 3620
loop do
  n = gets.to_i
  if n == 0 then exit end
  cnt = 0

  for i in 1 .. n / 2
    for a in 1 .. n / i
      if n == a * i + (a * (a - 1)) / 2
        cnt += 1
        :found
      end
    end
  end

  puts cnt
end


Measured memory_bytes: 6868
def BubbleSort(N, C):
    C = [] + C
    for i in range(N):
        for j in range(N-1, i, -1):
            if C[j][1] < C[j-1][1]:
                C[j], C[j-1] = C[j-1], C[j]
    return C

def SelectionSort(N, C):
    C = [] + C
    for i in range(N):
        minj = i
        for j in range(i, N):
            if C[minj][1] > C[j][1]:
                minj = j
        C[i], C[minj] = C[minj], C[i]
    return C

def CompareSuit(L1, L2):
    suit1, suit2 = "", ""
    for i in range(len(L1)):
        suit1 = suit1 + L1[i]
        suit2 = suit2 + L2[i]
    if suit1 == suit2:
        return "Stable"
    else:
        return "Not stable"

N = int(input())
C = input().split()

C1 = BubbleSort(N, C)
C2 = SelectionSort(N, C)

print(" ".join(C1))
print(CompareSuit(C1, C1))
print(" ".join(C2))
print(CompareSuit(C1, C2))

Measured memory_bytes: 7804
#include <stdio.h>

int main(){
  int n,i,j,k,m;
  char c[5000];
  int dp[5000][5000];
  scanf("%d",&n);
  scanf("%s",c);
  m=0;
  for(i=n-1;i>=0;i--){
    for(j=n-1;j>i;j--){
      if(c[i]==c[j]){
        k=1;
        if((i+1<n)&&(j+1<n)){
          k+=dp[i+1][j+1];
        }
        if(k>j-i){
          k=j-i;
        }
      }else{
        k=0;
      }
      if(k>m){
        m=k;
      }
      dp[i][j]=k;
    }
  }
  printf("%d",m);
  return(0);
}

Measured memory_bytes: 97792
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <random>
#include <ctime>
#include <bitset>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <cstring>
#include <queue>
#include <deque>
#include <stack>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#define ld long double
#define ull unsigned long long
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fast_io cout.tie(0), cin.tie(0), ios_base::sync_with_stdio(0)
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
using namespace std;
//using namespace __gnu_pbds;
//typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
ld eps = (ld)1 / 1e15;
ll mod2 = 998244353, mod1 = 1e9 + 7;
ll sqr(ll a) { return a * a; }
ll qb(ll a) { return a * a * a; }
ll gcd(ll a, ll b) { return !a ? b : gcd(b % a, a); }
ll binpow(ll a, ll b, ll mod) { return b ? (b % 2 ? (a * (sqr(binpow(a, b / 2, mod)) % mod)) % mod : sqr(binpow(a, b / 2, mod)) % mod) : 1; }
ll binmult(ll a, ll b, ll mod) { return b ? (b % 2 ? (2 * binmult(a, b / 2, mod) + a) % mod : (2 * binmult(a, b / 2, mod)) % mod) : 0; }
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

int main()
{
    //freopen("telecow.in", "r", stdin), freopen("telecow.out", "w", stdout);
    fast_io;
    ll n, m, i, v, s = 0;
    cin >> n >> m;
    for (i = 1; i <= m; i++)
    {
        cin >> v;
        s += v;
    }
    if (n - s >= 0) cout << n - s;
    else cout << -1;
    return 0;
}


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

#define REP(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)

int main(){
    int r,d,x;
    cin >> r >> d >> x;

    for(int i=0;i<10;i++){
        x = r * x - d;
        cout << x << endl;
    }

    return 0;
}

Measured memory_bytes: 256
import sys
n,m = map(int,input().split())

a = [0]*n
flag = [0]*n

for i in range(m):
    s,c = map(int,input().split())
    if s == 1 and c == 0 and n != 1:
        print(-1)
        sys.exit()

    if flag[s-1] == 0:
        flag[s-1] = 1
    else:
        #flag[s-1] == 1
        if a[s-1] != c:
            print(-1)
            sys.exit()
    a[s-1] = c



if a[0] == 0 and n != 1:
    a[0] = 1

print("".join(map(str,a)))


Measured memory_bytes: 9080
#include <iostream>
using namespace std;
int main(){
  int N,T,A,X;
  cin >> N >> T >> A;
  int res = 0;
  double cc = 1e18;
  for(int i = 1;i <= N;i++){
    cin >> X;
    int d = (T*1000-X*6)-A*1000;
    if(d<0)d=-d;
    if(cc>d)cc=d,res=i;//最小のものを判断して入うためにも、比較対象を出来るだけ大きくするのか？
  }
  cout << res;
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;
public class Main{

	public static void main(String[] args) throws Exception{
		int num = 998244353;

		// TODO Auto-generated method stub
 		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 		PrintWriter out = new PrintWriter(System.out);
 		int n = Integer.parseInt(bf.readLine());
 		long sum = 0;
 		for(int i =1;i<=n;i++){
 			sum+= (long)(i)*(long)((n-i+1));
 		}
 		for(int i = 0;i<n-1;i++){
//	 		String input1 = bf.readLine().trim();
//	 		String input2 = bf.readLine().trim();
	 		StringTokenizer st = new StringTokenizer(bf.readLine());
	 		int v1 = Integer.parseInt(st.nextToken());
	 		int v2 = Integer.parseInt(st.nextToken());
	 		int min = Math.min(v1, v2);
	 		int max = Math.max(v1,  v2);
	 		sum-=(long)(min)*(long)((n-max+1));
 		}
 		
 		
 		out.println(sum);
	 		
 		out.close();
 		
 		
 		
 	}
}
 	
 
//StringJoiner sj = new StringJoiner(" "); 
//sj.add(strings)
//sj.toString() gives string of those stuff w spaces or whatever that sequence is

 		
 		
 		
 		
	




Measured memory_bytes: 46708
#include<stdio.h>
int main() {
	int N;
	scanf("%d",&N);
	if (65<=N&&N<=90)
	{
		printf("1\n");
	}
	else if (97<=N&&N<=122)
	{
		printf("2\n");
	}
	else
	{
		printf("0\n");
	}
	return 0;
}


Measured memory_bytes: 2120
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
int n,yen,x,y,z;
bool tf=true;
cin>>n>>yen;
for(x=0;x<=n;x++)
{
for(y=0;y<=n;y++)
{
z=n-x-y;
if((x*10000+y*5000+z*1000==yen)&&(z>=0))
{
tf=false;
printf("%d %d %d",x,y,z);
goto syu;
}
}
}
syu:if(tf)
{cout<<"-1 -1 -1";}
return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int64_t MAXN = 15, INF = pow(10, 12), zero = 0;
int64_t N, K, ans = 0;
vector<int64_t> A(MAXN);

int64_t dfs(int64_t idx, int64_t cnt, int64_t cost, int64_t prevh)
{
  if (cnt == K)
    return cost;
  if (idx == N)
    return INF;
  if (A.at(idx) > prevh)
  {
    return dfs(idx + 1, cnt + 1, cost, A.at(idx));
  }
  int64_t a, b;
  a = dfs(idx + 1, cnt + 1, cost + (prevh - A.at(idx) + 1), prevh + 1);
  b = dfs(idx + 1, cnt, cost, prevh);
  return min(a, b);
}

int main()
{
  cin >> N >> K;
  for (int i = 0; i < N; i++)
    cin >> A.at(i);
  if (K != 1)
    ans = dfs(1, 1, 0, A.at(0));
  cout << ans << endl;
}

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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define hash dhsjakhd
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef long double ld;


unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
std::mt19937 eng(seed);

uniform_int_distribution<> DD(0, (1ll << 31));

ll random2(){
    return (ll(DD(eng))*(1ll << 31) + ll(DD(eng))) & ((1ll << 62ll)-1);
}

ll n,m,T,k,q;

const ll big = 1000000007;
const ll big2 = 1000000009;
const ll mod =  998244353;

const ll MAXN = 3001;

unordered_map<ll,ll> M;
vl A,B;

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

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

    ll a,b,c,d;

    cin >> n;
    rep(c1,0,n){
        cin >> a >> b;
        A.push_back(a);B.push_back(b);
    }
    ll ma = 0;
    rep(c1,0,n){
        rep(c2,0,n){
            if(c1 != c2){
                a = A[c2]-A[c1];
                b = B[c2]-B[c1];
                ll h = a*(3*big) + b;
                if(M.find(h) == M.end()){
                    M[h] = 0;
                }
                M[h]++;
                ma = max(ma, M[h]);
            }
        }
    }
    cout << n-ma << "\n";

    return 0;
}


Measured memory_bytes: 384
N = int(input())
array = list(map(int,input().split()))
ans = 0
while True:
    if max(array) == 0:
        break
    flg = False
    for i in range(N):
        if array[i] == 0:
            if flg:
                break
            continue
        array[i] -= 1
        flg = True
    ans += 1
print(ans)

Measured memory_bytes: 3060
# Vicfred
# https://atcoder.jp/contests/abc132/tasks/abc132_b
# implementation
n = int(input())
p = list(map(int,input().split()))

answer = 0
for i in range(1, n-1):
    if p[i-1] < p[i] < p[i+1] or p[i-1] > p[i] > p[i+1]:
        answer += 1

print(answer)



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

int main() {
    // ll N, A, B, C, D, E;
    // cin >> N >> A >> B >> C >> D >> E;
    ll N, A[5];
    cin >> N;
    rep(i, 5) cin >> A[i];
    sort(A, A + 5);

    ll mn = A[0];

    cout << (N + mn - 1) / mn + 4 << endl;


}

Measured memory_bytes: 3640
#include <iostream>
#include <vector>
#include <string.h>
#include <set>
#include <map>
#include <unordered_map>
#include <assert.h>
#include <algorithm>
#include <queue>
#include <bitset>
#include <stack>
#include <chrono>
#include <random>
#include <iomanip>
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define ll long long
#define INF 1000000000000000000
#define MOD 1000000007
#define rnd mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define uid uniform_int_distribution <int>
using namespace std;
// Read the question carefully and see all the given sample tests
// Think about the correctness before implementing

int main() {
	int n, K;
	cin >> n >> K;
	vector <int> present(10);
	for (int i = 0; i < K; i++) {
		int x;
		cin >> x;
		present[x] = 1;
	}
	auto valid = [&](vector<int> v) {
		int p = 0;
		while(p < 5 && v[p] == 0) p++;
		bool ok = true;
		for (int i = p; i < 5; i++) {
			ok &= (!present[v[i]]);
		}
		return ok;
	};
	int ans = MOD;
	for (int i = 0; i < 10; i++)
		for (int j = 0; j < 10; j++)
			for (int k = 0; k < 10; k++)
				for (int l = 0; l < 10; l++)
					for (int m = 0; m < 10; m++) {
						if (i * 10000 + j * 1000 + k * 100 + l * 10 + m >= n
						 && valid({i, j, k, l, m})) {
							ans = min(ans, i * 10000 + j * 1000 + k * 100 + l * 10 + m);
						}
					}
						
		
	cout << ans;	
}
		


Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    int H,W,i,j,g;
    for(;;){
        scanf("%d %d\n",&H,&W);
        if(H==0&&W==0)break;
        for(g=1;g<=H;g++){
            for(j=1;j<=W;j++){
                putchar('#');
            }
            putchar('\n');
        }
        putchar('\n');
    }
    
    return 0;
    
}


Measured memory_bytes: 2084
N = int(input())
A = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    A[a-1].append(b-1)
    A[b-1].append(a-1)

B = [False]*N
visited = [True]*N

Fp,Sp = 0,0
Fi,Si = [0],[N-1]

while B != visited:
    # Fennec
    nextXi = []
    for i in Fi:
        if not B[i]:
            B[i] = True
            Fp += 1
            nextXi.extend(A[i])
    Fi = nextXi
    # Snuke
    nextXi = []
    for i in Si:
        if not B[i]:
            B[i] = True
            Sp += 1
            nextXi.extend(A[i])
    Si = nextXi

print("Fennec" if Fp>Sp else "Snuke")

Measured memory_bytes: 22896
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,m,a;
  int ans = 0;
  cin >> n >> m;

  for(int i = 0;i < m;i++){
    cin >> a;
    ans += a;
  }
  if(n >= ans)cout << n - ans << endl;
  else cout << -1 << endl;
}

Measured memory_bytes: 3648
#include <stdio.h>
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <map>

//#include <bits/stdc++.h>
using namespace std;
#define print(x) cout<<(x)<<endl
#define prints(x, y) cout<<(x)<<" "<<(y)<<endl
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define ll long long int
#define pb push_back

int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  int ans = min(b, d) - max(a, c);
  if(ans < 0) print(0);
  else print(ans);
}


Measured memory_bytes: 888
#include<iostream>
#include<vector>
#include<cstdint>
using namespace std;

const int MOD = 1000000007; // 今回使う余り

int64_t pow(int x, int y) {
	switch (y) {
		case 0: return 1;
		case 1: return x;
		case 2: return (int64_t)x * x % MOD;
	}
	return pow(pow(x, y >> 1), 2) * pow(x, y & 1) % MOD;
}
int C(int x, int y) {
	int64_t ans = 1;
	for (int i = 0;i < y;++ i) {
		ans *= (x - i) * pow(i + 1, MOD - 2) % MOD;
		ans %= MOD;
	}
	return ans;
}

int H(int x, int y) {
	return C(x + y - 1, y);
}

int main() {
	int N, M;
	cin >> N >> M;
	
	vector<pair<int, int> > primes; // 素因数分解の結果
	for (int i = 2, c;i * i <= M;++ i) { // 試し割り
		c = 0; // cは割った回数
		while (M % i == 0) {
			++ c;
			M /= i;
		}
		if (c != 0) primes.push_back(make_pair(i, c));
	}
	if (M > 1) primes.push_back(make_pair(M, 1));
	
	int64_t ans = 1;
	for (int i = 0;i < primes.size();++ i) {
		ans *= H(N, primes[i].second);
		ans %= MOD;
	}
	cout << ans;
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり
また、コンテスト後に https://31536000.hatenablog.com/ で解説していると思うので、良かったら読んでねー

要するに？Mを素因数分解します。
例えばサンプル1だと、6を素因数分解すると2と3です
後は、全ての要素を1にした数列aに対しこの数を割り振る方法なので、割り振り方を考えます
サンプル2だと、12=2^2*3なのでこれを考えてみましょう
まず3はN通り、次に2を2つ割り振る方法はNH2=(N+1)C2=6通り
結論から言うと、Mの素因数分解した結果がΠ(x_i)^(y_i)ならばΠ(x_i)H(y_i)です
*/

Measured memory_bytes: 256
#include <iostream>
#include <atcoder/convolution>
using namespace std;
using namespace atcoder;

int main() {
	int N, M;
	cin >> N >> M;
	vector<long long> A(N), B(M);
	for (int i = 0; i < N; i++) cin >> A[i];
	for (int i = 0; i < M; i++) cin >> B[i];
	vector<long long> C = convolution(A, B);
	for (auto c : C) cout << c << " ";
	cout << endl;
}


Measured memory_bytes: 27248
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1e6;
ll comb[1005][1005]={0};
vector<ll> node[1005];
void comb_set(ll n)
{
	comb[1][0]=1;
	comb[1][1]=1;
	for(int i=2;i<=n;i++){
		comb[i][0]=1;
		for(int j=1;j<=n;j++)
			comb[i][j]=(comb[i-1][j-1]+comb[i-1][j])%mod;
	}
}
P dfs(int pos){
	if(node[pos].size()==0){
		return P(1,1);
	}
	ll node_num=0,ans=1;
	vector<P> son_data;
	for(int i=0;i<node[pos].size();i++){
		int son=node[pos][i];
		son_data.push_back(dfs(son));
		node_num+=son_data[i].second;
	}
	
	ll ret2=node_num+1;
	
	int n=son_data.size();
	for(int i=0;i<n;i++){
		ans*=comb[node_num][son_data[i].second];
		ans%=mod;
		ans*=son_data[i].first;
		ans%=mod;
		node_num-=son_data[i].second;
	}
	
	return P(ans,ret2);
}
int main(void){
	ll n;
	cin>>n;
	comb_set(n);
	
	bool lose[1005];
	for(int i=0;i<1005;i++)
		lose[i]=true;
	for(int i=1;i<n;i++){
		int a,b;
		cin>>a>>b;
		lose[b]=false;
		node[a].push_back(b);
	}
	
	int st;
	for(int i=1;i<=n;i++)if(lose[i])st=i;
	
	cout<<dfs(st).first<<endl;
}


Measured memory_bytes: 11084
import java.util.*;
import java.io.*;
import java.text.*;
//Solution Credits: Taranpreet Singh
public class Main{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int n = ni(), k = ni();
        long[] h = new long[1+n], dp = new long[1+n];
        for(int i = 1; i<= n; i++)h[i] = nl();
        Arrays.fill(dp, IINF);
        dp[1] = 0;
        for(int i = 1; i<= n; i++)
            for(int j = 1; j<= k && i-j>0; j++)
                dp[i] = Math.min(dp[i], dp[i-j]+Math.abs(h[i]-h[i-j]));
        pn(dp[n]);
    }
    //SOLUTION END
    void hold()throws Exception{throw new Exception("Hold right there, Sparky!");}
    long mod = (long)1e9+7, IINF = (long)4e18;
    final int INF = (int)2e9, MX = (int)1e6+1;
    DecimalFormat df = new DecimalFormat("0.000000000000000");
    double PI = 3.1415926535897932384626433832792884197169399375105820974944, eps = 1e-8;
    static boolean multipleTC = false, memory = false;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        int T = (multipleTC)?ni():1;
        //Solution Credits: Taranpreet Singh
        pre();for(int i = 1; i<= T; i++)solve(i);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
        else new Main().run();
    }
    long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
    int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n(){return in.next();}
    String nln(){return in.nextLine();}
    int ni(){return Integer.parseInt(in.next());}
    long nl(){return Long.parseLong(in.next());}
    double nd(){return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next(){
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        String nextLine(){
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                e.printStackTrace();
            }  
            return str;
        }
    }
}    

Measured memory_bytes: 35868
def fin(ok)
  puts ok ? 'Yes' : 'No'
  exit
end

gets.strip.chars.each_with_index do |c, i|
  j = i + 1 
  next if j.even? && ['L', 'U', 'D'].include?(c)
  next if j.odd? && ['R', 'U', 'D'].include?(c)
  fin false
end
fin true



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

int main()
{
	char s[20];
	scanf("%s",s);
	int len=strlen(s);
	int sum=0;
	int vis=0;
	for(int i=1;i<len;i++)
	{
		sum+=9;
		if(s[i]!='9')
		   vis=1;
	}
	if(vis)
	   sum+=s[0]-'0'-1;
    else
	   sum+=s[0]-'0';
	printf("%d\n",sum);
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <assert.h>
#include <numeric>
#include <math.h>
#include <climits>

using namespace std;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
typedef long long ll;

template <typename T>
T gcd(T a, T b) {
    if(a < b) gcd(b, a);
    if (b == 1) return 1;
    T r;
    while ((r=a%b)) {
        a = b;
        b = r;
    }
    return b;
}

#define MOD (1000000000+7)

int dp[3001][3001];
int main() {
    string s, t;
    cin >> s >> t;
    REP(i, s.size()) {
        for (int j = 0; j < t.size(); j++){
            if (s[i] == t[j]) {
                dp[i+1][j+1] = dp[i][j]+1;
            } else {
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
            }
        }
    }
    
    int i = s.size();
    int j = t.size();
    string ans = "";
    while (i > 0 && j > 0) {
        if (dp[i][j] == dp[i-1][j]) i--;
        else if (dp[i][j] == dp[i][j-1]) j--;
        else {
            ans = s[i-1] + ans;
            i--;j--;
        }
    }
    
    cout << ans << endl;
}


Measured memory_bytes: 35456
#include<iostream>
#include<map>
#include<queue>
using namespace std;
const long LIM=1e18;
int T;
long N,A,B,C,D;
main()
{
	cin>>T;
	for(;T--;)
	{
		cin>>N>>A>>B>>C>>D;
		long X[3]={2,3,5},Y[3]={A,B,C};
		long ans=60*(A+D);
		map<long,long>all;
		all[N]=0;
		priority_queue<pair<long,long> >Q;
		Q.push(make_pair(-N,0L));
		while(!Q.empty())
		{
			long t=-Q.top().first,c=Q.top().second;Q.pop();
			if(all[t]<c||ans<=c)continue;
			if(t<=ans/D)
			{
				ans=min(ans,c+t*D);
			}
			for(int i=0;i<3;i++)
			{
				long a=t%X[i],b=t/X[i];
				if(a*D+c+Y[i]<ans)
				{
					long nc=a*D+c+Y[i];
					if(all.find(b)==all.end()||all[b]>nc)
					{
						Q.push(make_pair(-b,nc));
						all[b]=nc;
					}
				}
				if((X[i]-a)*D+c+Y[i]<ans)
				{
					long nc=(X[i]-a)*D+c+Y[i];
					if(all.find(b+1)==all.end()||all[b+1]>nc)
					{
						Q.push(make_pair(-b-1,nc));
						all[b+1]=nc;
					}
				}
			}
		}
		cout<<ans<<endl;
	}
}

Measured memory_bytes: 4632
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x) (x).begin(), (x).end()
#define rep(i, s, n) for (i64 i = (s), i##_limit = (n); i < i##_limit; ++i)
#define repr(i, s, t) for (i64 i = (s), i##_limit = (t); i >= i##_limit; --i)
#define repc(i, s, t) for (i64 i = (s), i##_limit = (t); i <= i##_limit; ++i)
#define var(type, ...) \
    type __VA_ARGS__;  \
    read(__VA_ARGS__);
#ifndef DBG
#define dump(...)
#endif
using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template <class T, class U>
inline bool chmax(T &a, const U &b) {
    return b > a && (a = b, true);
}
template <class T, class U>
inline bool chmin(T &a, const U &b) {
    return b < a && (a = b, true);
}
constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

template <class T>
inline vector<T> makeV(const T &initValue, size_t sz) {
    return vector<T>(sz, initValue);
}

template <class T, class... Args>
inline auto makeV(const T &initValue, size_t sz, Args... args) {
    return vector<decltype(makeV<T>(initValue, args...))>(
        sz, makeV<T>(initValue, args...));
}

template <class T>
inline istream &operator>>(istream &is, vector<T> &vec) {
    for (auto &e : vec) is >> e;
    return is;
}

inline void read() {}

template <class Head, class... Tail>
inline void read(Head &head, Tail &... tail) {
    cin >> head;
    read(tail...);
}

inline void print() { cout << "\n"; }

template <class Head, class... Tail>
inline void print(Head &&head, Tail &&... tail) {
    cout << head;
    if (sizeof...(tail)) cout << ' ';
    print(forward<Tail>(tail)...);
}

template <class T>
inline ostream &operator<<(ostream &os, const vector<T> &vec) {
    static constexpr const char *delim[] = {" ", ""};
    for (const auto &e : vec) os << e << delim[&e == &vec.back()];
    return os;
}

template <class Container>
struct Rev {
    Container &x_;
    inline Rev(Container &x) : x_(x) {}
    inline auto begin() { return rbegin(x_); }
    inline auto end() { return rend(x_); }
};
// }}} End Header

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.setf(ios_base::fixed);
    cout.precision(12);

    var(int, N, M);

    bool f1[200100]{};
    bool f2[200010]{};

    rep(i, 0, M) {
        var(int, a, b);
        --a, --b;
        if (a > b) swap(a, b);
        if (a == 0) f1[b] = true;
        if (b == N - 1) f2[a] = true;
    }

    bool ok = false;
    rep(i, 0, N) {
        if (f1[i] && f2[i]) {
            ok = true;
        }
    }

    print(ok ? "POSSIBLE" : "IMPOSSIBLE");

    return 0;
}


Measured memory_bytes: 640