akhauriyash/Code-Regression huggingface dataset:
#![allow(unused_imports, unused_variables, dead_code)]
use std::io::*;
use std::fmt::*;
use std::str::*;
use std::cmp::*;
use std::collections::*;

trait InputValue {
    fn parse(s: &str) -> Self;
}

fn read<T: InputValue>() -> T {
    let mut buf = String::new();
    let _ = stdin().read_line(&mut buf);
    T::parse(&buf.trim())
}

fn readnc<T: InputValue>() -> Vec<T> {
    let mut vec = vec![];
    let line: String = read();
    for token in line.split_whitespace() {
        vec.push(T::parse(token));
    }
    vec
}

fn readn<T: InputValue>(n: usize) -> Vec<T> {
    let mut vec = vec![];
    for _ in 0..n {
        vec.push(read());
    }
    vec
}

macro_rules! parse_single_value {
    ($($t:ty),*) => {
        $(
            impl InputValue for $t {
                fn parse(s: &str) -> $t { s.parse().unwrap() }
            }
        )*
	}
}
parse_single_value!(i32, i64, f32, f64, usize, String);

macro_rules! parse_tuple {
	($($t:ident),*) => {
		impl<$($t),*> InputValue for ($($t),*) where $($t: InputValue),* {
			fn parse(s: &str) -> ($($t),*) {
				let mut tokens = s.split_whitespace();
				let t = ($($t::parse(tokens.next().unwrap())),*);
				t
			}
		}
	}
}
parse_tuple!(A, B);
parse_tuple!(A, B, C);

// ===

fn main() {
    let (h, w): (i64, i64) = read();
    println!("{}", min(solve(h, w), solve(w, h)));
}

fn solve(h: i64, w: i64) -> i64 {
    if w % 3 == 0 {
        return 0;
    }
    let mut ans = h;
    for i in 1..w {
        let a0 = h * i;
        let j = w - i;
        let a1 = (h / 2) * j;
        let a2 = (h - h / 2) * j;
        ans = min(ans, max(a0, max(a1, a2)) - min(a0, min(a1, a2)));
    }
    ans
}


Measured memory_bytes: 4352
A=[]
h,w=map(int,input().split())
for i in range(h):
	s=input()
	if s.count("#")!=0:
		A.append(s)
B=[]
C=[]
for i in range(w):
	cnt=0
	for j in range(len(A)):
		if A[j][i]==".":
			cnt+=1
	if cnt==len(A):
		B.append(i)
for i in range(w):
	c=""
	for j in range(len(A)):
		if i not in B:
			c+=A[j][i]
	if len(c)>0:
		C.append(c)
for j in range(len(C[0])):
	p=""
	for i in range(len(C)):
		p+=C[i][j]
	print(p)


Measured memory_bytes: 3064
import java.util.Scanner;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String str = sc.nextLine();
    int num1 = Integer.parseInt(str);
    int a = Integer.parseInt(""+str.charAt(0));
    int b = Integer.parseInt(""+str.charAt(1));
    int c = Integer.parseInt(""+str.charAt(2));
    int num2 = 100*c+10*b+a;
    if(num1==num2){
      System.out.println("Yes");
    }else{
      System.out.println("No");
    }
  }
}

Measured memory_bytes: 21972
#include <bits/stdc++.h>
using namespace std;
struct Fast {Fast() {std::cin.tie(0); ios::sync_with_stdio(false);}} fast;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define mp make_pair
#define MOD 1000000007


int main() {
    int N, M;
    cin >> N >> M;
    vi G[10] = {};
    rep(i, M) {
        int a, b; cin >> a >> b;
        a--, b--;
        G[a].pb(b);
        G[b].pb(a);
    }

    vi v;
    rep(i, N-1) v.pb(i+1);
    int ans = 0;

    do {
        bool f = true;

        int c = 0, d = v[0];
        auto itr = find(all(G[c]), d);
            if (itr == G[c].end()) {
                f = false;
            }

        rep(i, N - 2) {
            int a = v[i], b = v[i + 1];
            auto itr = find(all(G[a]), b);
            if (itr == G[a].end()) {
                f = false;
                break;
            }
        }
        if (f) ans++;

    } while (next_permutation(all(v)));

    cout << ans << endl;

}


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

#include <iostream>
#include <vector>
#include <deque>
#include <queue>
#include <map>
#include <algorithm>


using namespace std;

#define Max INT_MAX
#define Inf (INT_MAX/2)
#define Min INT_MIN


#define rep(i, n) for(int i = 0; i < n; i++)
#define repi(i,l,n) for(int (i)=(int)(l);(i)<(int)(n);(i)++)
// s <= x < g ?
#define IN(x,s,g) ((x) >= (s) && (x) < (g))
// 0 <= x < w && 0 <= y < h ?
#define ISIN(x,y,w,h) (IN((x),0,(w)) && IN((y),0,(h)))

typedef pair<int, int> P;

int main()
{
    int n;
    long long dp[30] = {0};
    while( cin >> n ){
        if( n == 0 ) { break;}
        rep(i,30){
            dp[i] = 0;
        }
        rep(i,3){
            dp[i] = 1;
        }
        repi(i,0,30){
            if( IN(i-1,0,30) ) { dp[i] += dp[i-1];}
            if( IN(i-2,0,30) ) { dp[i] += dp[i-2];}
            if( IN(i-3,0,30) ) { dp[i] += dp[i-3];}
        }

        //rep(i,30){
        //    cout << dp[i] << ",";
        //}

        long long sum = 0;

        //cout << "dp[29] = " << dp[29] << endl;
        sum = dp[n-1];
        int ans = sum / 3650;
        if( !(sum % 3650 == 0) ) { 
            ans++;
        } 
        cout << ans << endl;
    }
}

Measured memory_bytes: 1156
#include<iostream>
#include<numeric>
#include<set>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
typedef long long li;
#define repa(i,a,n) for(int i=(a);i<(n);i++)
#define MOD 1000000000
#define rep(i,n) for(int i=0;i<(n);i++)

#define df 0
template<class T> void print(const T& t){ cout << t << "\n"; }
template<class T, class... Ts> void print(const T& t, const Ts&... ts) { cout << t; if (sizeof...(ts)) cout << " "; print(ts...); }
// // Container コンテナ型, map以外
// template< template<class ...> class Ctn,class T>
// std::ostream& operator<<(std::ostream& os,const Ctn<T>& v){
//   // ここでストリームに obj を書き込みます。
//   auto itr=v.begin();
//   while(itr!=v.end()){
//     if(itr!=v.begin())cout << " ";
//     cout << *(itr++);
//   }
//   return os;
// }


int main(){
  int n,cnt=1; cin >>n;
  int flag=0,tmp; cin >>tmp;
  rep(i,n-1){
    int a; cin >>a;
    if(flag){
      if(flag*(a-tmp)<0){
        cnt++;
        flag=0;
      }
    }else{
      flag=(a>tmp)-(a<tmp);
    }
    tmp=a;
  }
  print(cnt);
}



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

int main(void){
    char str[1200];
    scanf("%[^\n]", str);
    for(int i=0; i<strlen(str); i++){
        if(str[i] >= 97 && str[i] <= 122) printf("%c", str[i]-32);
        else if(str[i] >= 65 && str[i] <= 90) printf("%c", str[i]+32);
        else printf("%c", str[i]);
    }
    printf("\n");
    return 0;
}


Measured memory_bytes: 2076
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<pi> vpi;
typedef vector<vi> vii;
typedef map<int, int> mp;
typedef multiset<int> mset;
typedef long int int32;
typedef unsigned long int uint32;
typedef long long int int64;
typedef unsigned long long int  uint64;
typedef vector<int64> vi64;
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define form(i,j,k,l) for(int i=j;i<int(k);i+=l)
#define rform(i,j,k,l) for(int i=int(j);i>int(l);i-=l)
#define rep(i, j) for(int i=0;i<int(j);i++)
#define rrep(i, j) for(int i=int(j);i>=0;i--)
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define forc(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define IN(A, B, C) assert( B <= A && A <= C)
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define INF (int)1e9
#define INF64 (int64)1e18
#define EPS 1e-9
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
#define read(type) readInt<type>()
#define F first
#define S  second
const double pie = acos(-1.0);
template <typename T>
T Max(T x, T y)
{
  return (x > y) ? x : y;
}
template <typename T>
T Min(T x, T y)
{
  return (x > y) ? y : x;
}
int gcd(int n1, int n2)
{
  if (n2 != 0) return gcd(n2, n1 % n2);
  else return n1;
}
#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1 << " | "; __f(comma + 1, args...);
}
#else
#define trace(...)
#endif
clock_t time_p = clock();
void rtime() { time_p = clock() - time_p; cerr << "Time Taken : " << (float)1000 * (time_p) / CLOCKS_PER_SEC << "\n";}
int64 binpow(int64 a, int64 b, int64 m) {
  a %= m;
  int64 res = 1;
  while (b > 0) {
    if (b & 1)
      res = res * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return res;
}
int main()
{ fast;
  int x1, y1, x2, y2;
  cin >> x1 >> y1 >> x2 >> y2;
  int  r1 = x2 - x1;
  int u1 = y2 - y1;
  int l2 = x2 - x1;
  int d2 = y2 - y1;
  for (int i = 0; i < r1; i++)
    cout << "R";
  for (int i = 0; i < u1; i++)
    cout << "U";
  for (int i = 0; i < l2; i++)
    cout << "L";
  for (int i = 0; i < d2; i++)
    cout << "D";
  cout << "L";
  for (int i = 0; i < u1 + 1; i++)
    cout << "U";
  for (int i = 0; i < r1 + 1; i++)
    cout << "R";
  cout << "D";
  cout << "R";
  for (int i = 0; i < d2 + 1; i++)
    cout << "D";
  for (int i = 0; i < l2 + 1; i++)
    cout << "L";
 cout<<"U";

}



Measured memory_bytes: 3596
#include<stdio.h>
#include<string.h>

#define MAX 1000000

typedef struct{
  int time;
  char name[10];
}queue;

queue Q[MAX];
int head,tail;

void enqueue(queue);
queue dequeue(void);

int main(){
  int i,n,Time,sum;
  queue q;

  scanf("%d %d",&n,&Time);
  for(i=0;i<n;i++){
    scanf("%s",Q[i].name);
    scanf("%d",&Q[i].time);
  }

  sum = 0;
  head = 0;
  tail = n;

  while(head != tail){
    q = dequeue();
    if(q.time <= Time){
      sum += q.time;
      printf("%s %d\n",q.name,sum);
    }
    else {
      q.time -= Time;
      enqueue(q);
      sum += Time;
    }
  }

  return 0;
}

void enqueue(queue q){

  Q[tail] = q;
  tail++;
}

queue dequeue(){
  queue q;

  q = Q[head];
  head++;
  return q;
}

Measured memory_bytes: 4696
#include<iostream>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip>//setprecision
#include<math.h>
#include <functional>
#include<climits>
using namespace std;
template <typename T> bool chmax(T &u, const T z) { if (u < z) {u = z; return true;} else return false; }
template <typename T> bool chmin(T &u, const T z) { if (u > z) {u = z; return true;} else return false; }
#define ll  long long 
const ll INF=1LL<<60;
const ll MOD=1000000007;
#define rep(i, n)        for(ll i=0; i<(ll)(n); ++i)
ll dp[2001];
int main(){
    ll a;cin>>a;
    vector<ll>b(a),c(a);
    rep(i,a){
        ll d,e;
        cin>>d>>e;
        b[i]=d+e;
        c[i]=d-e;
    }
    sort(b.begin(),b.end());
        sort(c.begin(),c.end());
        ll ans=max(abs(b[0]-b[a-1]),abs(c[0]-c[a-1]));
        cout<<ans;
}

Measured memory_bytes: 6424
h, w = map(int, input().split())
A = [list(input()) for i in range(h)]


def dfs(x, y):
    A[x][y] = '.'

    if x == h-1 and y == w-1:
        return
    elif x+1 < h and A[x+1][y] == '#':
        dfs(x+1, y)
    elif y+1 < w and A[x][y+1] == '#':
        dfs(x, y+1)
    else:
        return


dfs(0, 0)
if A == [['.'] * w] * h:
    print('Possible')
else:
    print('Impossible')

Measured memory_bytes: 3064
#factorial
MOD = 998244353 

N, M, K = map(int, input().split()) 

modinv_t = [0, 1]
modfact_t = [1, 1]
modfactinv_t = [1, 1]
for i in range(2,N+1):
  modfact_t.append(modfact_t[-1] * i % MOD)
  modinv_t.append(modinv_t[MOD%i] * (MOD-(MOD//i)) % MOD)
  modfactinv_t.append(modfactinv_t[-1] * modinv_t[-1] % MOD)
# permutation
def nPr(n, r):
  return  modfact_t[n] * modfactinv_t[n-r] % MOD
# combination
def nCr(n, r):
  return  modfact_t[n] * modfactinv_t[n-r] * modfactinv_t[r] % MOD
#
def nHr(n, r):
  return  nCr(n+r-1,r)
#


t = M*pow(M-1,N-1,MOD)
for i in range(1,K+1):
  t += M*pow(M-1,N-1-i,MOD)*nCr((N-1),i)
  t %= MOD
#
t %= MOD
print(t)


Measured memory_bytes: 32760
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<stack>
#include<vector>
#include<queue>
#include<set>
#include<utility>
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define ll long long
using namespace std;
int s1[100005];
int s2[100005];
int s3[100005];
bool cmp(int a, int b) {
	return a>b;
}
priority_queue<int, vector<int>, greater<int>> q;
int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int x, y, a, b, c;
	cin >> x >> y >> a >> b >> c;
	for (int i = 0; i < a;i++) {
		cin >> s1[i];
	}
	for (int j = 0; j < b;j++) {
		cin >> s2[j];
	}
	for (int i = 0; i < c;i++) {
		cin >> s3[i];
	}
	sort(s1, s1 + a,cmp);
	sort(s2, s2 + b,cmp);
	for (int i = 0; i < x;i++) {
		q.push(s1[i]);
	}
	for (int i = 0; i < y;i++) {
		q.push(s2[i]);
	}
	sort(s3, s3 + c);
	int posc = 0;
	ll sum = 0;
	while (posc<c) {
		if (q.empty()) {
			break;
		}
		int p = q.top();
		q.pop();
		if (p>s3[posc]) {
			q.push(p);
		}
		else {
			q.push(s3[posc]);
		}
		posc++;
	}
	while (!q.empty()) {
		sum += q.top();
		q.pop();
	}
	cout << sum << endl;
	return 0;
}


Measured memory_bytes: 2552
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
#define rep(i,m,n) for(int i=m;i<n;i++)
#define co(n) cout<<n<<endl
#define all(n) (n).begin(),(n).end()
#define pb(n,m) n.push_back(m)
#define pi(n,m) n.insert(n.begin(),m);
#define ee(n) n.erase(n.end()-1)
#define eb(n) n.erase(n.begin())
#define check(n) reverse(all(n));rep(z,0,n.size())cout<<n[z];co("");reverse(all(n));
using namespace std;
namespace mp=boost::multiprecision;
typedef long long ll;
typedef unsigned long long ull;
using bint=mp::cpp_int;

int main(){
  vector<string> ans={};
  string s;
  int n;
  cin>>n;
  rep(i,0,n){
    cin>>s;
    pb(ans,s);
  }
  sort(all(ans));
  int c=1;
  rep(i,1,n) if(ans[i-1]!=ans[i]) c++;
  co(c);
  return 0;
}

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

int main()
{
	int i,j;
	int a[4];
	int b[4];
	while(cin >> a[0]){

		int hit =  0;
		int blow = 0;
		for(i=1;i<4;++i)cin>>a[i];
		for(i=0;i<4;++i)cin>>b[i];

		for(i=0;i<4;++i){
			for(j=0;j<4;++j){
				if(b[i] == a[j]){
					(j == i) ? ++hit : ++blow;
				}
			}
		}
		cout << hit << ' ' << blow << endl;
	}
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) for(int i=0;i<(n);++i)
#define repr(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

template<typename T>
void print(vector<T> &x) {
    int n = x.size();
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(vector<vector<T>> &x) {
    int n = x.size();
    rep(i,n) {
        rep(j,x[i].size()) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

vector<string> s;
ll sumU[2222][2222] = {0};
ll sumR[2222][2222] = {0};
ll sumD[2222][2222] = {0};
ll sumL[2222][2222] = {0};
 
int n,m;
 
int main(int argc, char const *argv[]) {
    cin >> n >> m;
    s.resize(n);
    rep(i,n) cin >> s[i];
 
    // U
    for (int j = 0; j < m; ++j) {
        for (int i = 1; i < n; ++i) {
            if (s[i][j] == '.') {
                if (s[i-1][j] == '#') sumU[i][j] = sumU[i-1][j];
                else sumU[i][j] = sumU[i-1][j]+1;
            }
        }
    }
 
    // D
    for (int j = 0; j < m; ++j) {
        for (int i = n-2; i >= 0; --i) {
            if (s[i][j] == '.') {
                if (s[i+1][j] == '#') sumD[i][j] = sumD[i+1][j];
                else sumD[i][j] = sumD[i+1][j]+1;
            }
        }
    }
 
    // L
    for (int i = 0; i < n; ++i) {
        for (int j = 1; j < m; ++j) {
            if (s[i][j] == '.') {
                if (s[i][j-1] == '#') sumL[i][j] = sumL[i][j-1];
                else sumL[i][j] = sumL[i][j-1]+1;
            }
        }
    }
 
    // R
    for (int i = 0; i < n; ++i) {
        for (int j = m-2; j >= 0; --j) {
            if (s[i][j] == '.') {
                if (s[i][j+1] == '#') sumR[i][j] = sumR[i][j+1];
                else sumR[i][j] = sumR[i][j+1]+1;
            }
        }
    }
 
    ll ans = 0;
 
    rep(i,n) {
        rep(j,m) {
            ll U = sumU[i][j];
            ll R = sumR[i][j];
            ll D = sumD[i][j];
            ll L = sumL[i][j];
            // printf("i = %d, j = %d ,U = %lld, R = %lld, D = %lld, L = %lld\n", i, j, U, R, D, L);
            chmax(ans,L+R+U+D);
        }
    }
 
    cout << ans+1 << endl;
 
    return 0;
}

Measured memory_bytes: 149760
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <numeric>




typedef long long ll;
#define PI 3.14159265359
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define mp make_pair
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define decp(n) cout<<fixed<<setprecision((int)n)
#define _GLIBCXX_DEBAC
#include <functional>
/*map<Keyの型, Valueの型> 変数名;
queue<型> 変数名;
priority_queue<型> 変数名;
priority_queue<型, vector<型>, greater<型>> 変数名;*/
//copy(v1.begin(), v1.end(), back_inserter(v2));
using namespace std;

ll gcd(ll a, ll b) {
	ll c;
	if (a < b) {
		c = a; a = b; b = c;
	}
	while (b != 0) {
		c = a % b; a = b; b = c;
	}
	return a;
}

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

int sort_greater(int m, int n) {
	vector<int> a(m);
	for (int i = 0; i < m; i++) {
		cin >> a[i];
	}
	sort(a.begin(), a.end(), greater<int>());
	for (int i = 0; i < n; i++) {
		cout << a[i];
	}
	return 0;
}

int bubblesort(int a[], int n) {
	int sw = 0;
	bool flag = 1;
	for (int i = 0; flag; i++) {
		flag = 0;
		for (int j = n - 1; j >= i + 1; j--) {
			if (a[j] < a[j - 1]) {
				swap(a[j], a[j - 1]);
				flag = 1;
				sw += 1;
			}
		}
	}
	return sw;
}

int a_z()
{
	for (int i = 0; i <= ('Z' - 'A'); i++) {
		cout << (char)('A' + i);
	}
	return 0;
}

int selecttionsort(int a[], int n) {
	int t, sw = 0, minj;
	for (int i = 0; i < n - 1; i++) {
		minj = i;
		for (int j = 0; j < n - 1; j++) {
			if (a[j] < a[minj]) {
				minj = j;
			}
		}
		t = a[i]; a[i] = a[minj]; a[minj] = t;
		if (i != minj) sw += 1;

	}
	return sw;
}

bool is_prime(int x) {
	if (x <= 1) return false;
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0) return false;
	}
	return true;
}

const ll mod = 1000000007;

map<string, int> memo;

using P=pair<int, int>;
/*void dfs(int v, int p = -1) {
	for (int u : to[v]) {
		if (u == p) continue;
		ans[u] += ans[v];
		dfs(u, v);
	}
}*/
ll findIndex(int value, vector<ll> a)
{

	for (ll i = 0; i < (ll)a.size(); i++) {
		if (a[i] == value) {
			return i;
		}
	}
	return -1;
}

ll nCr(ll n, ll r) {
	ll a = 1;
	for (ll i = n; i > n - r; --i) {
		a = a * i;
	}
	for (ll i = 1; i < r + 1; ++i) {
		a = a / i;
	}
	return a;
}

void comb(vector<vector <long long int> >& v) {
	for (ll i = 0; i < v.size(); i++) {
		v[i][0] = 1;
		v[i][i] = 1;
	}
	for (ll k = 1; k < v.size(); k++) {
		for (ll j = 1; j < k; j++) {
			v[k][j] = (v[k - 1][j - 1] + v[k - 1][j]);
		}
	}
}



int main() {
	int n;
	string s,t;
	cin >> s >> t;
	bool a = true;
	rep(i, s.size()) {
		if (s[i] != t[i])a = false;
	}
	if (a == true)cout << "Yes";
	else cout << "No";
	return 0;
}













Measured memory_bytes: 3600
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <cmath>

typedef long long ll;
const ll MOD = 1e9 + 7;

using namespace std;

int main(){
    ll n, s;
    cin >> n >> s;
    vector<ll> w(n);
    vector<ll> v(n);
    for(ll i = 0; i < n; i++){
        cin >> w[i] >> v[i];
    }

    ll dp[n+1][s+1];
    for(ll i = 0; i <= n; i++){
        for(ll j = 0; j <= s; j++){
            dp[i][j] = 0;
        }
    }
    for(ll i = 0; i < n; i++){
        for(ll j = 0; j <= s; j++){
            if(w[i] <= j){
                dp[i+1][j] = max(dp[i][j-w[i]]+v[i],dp[i][j]);
            } else{
                dp[i+1][j] = dp[i][j];
            }
        }
    }

    cout << dp[n][s] << endl;

    return 0;
}

Measured memory_bytes: 79104
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
int cl(int a, int b) {
	return (a - (a%b)) / b;//b=0だと積む
}
int up(int a, int b) {
	return cl(a + b - 1, b);//b=0だと積む
}
int ord(int a, int p) {
	if (a%p == 0) {
		return ord(a / p, p) + 1;
	}
	else {
		return 0;
	}
}
long long ruin(int a, int n, long long  p) {
	if (n == 0) {
		return (1 % p);
	}
	else {
		long long x = ruin(a, (n - (n % 2)) / 2, p);
		if (n % 2 == 0) {
			return (x*x) % p;
		}
		else {
			return (((x*x) % p)*a) % p;

		}

	}

}
long long com(int n, int r, int p) {
	if (r == 0) {
		return (1 % p);
	}
	else {
		long long x = com(n, r - 1, p);
		return (x*(n - r) / r) % p;
	}
}
long long sum(long long n, long long p) {
	if (n == 0) {
		return 0;
	}
	else {
		long long x = (n%p) + sum((n - (n%p)) / p, p);
		return x;
	}
}
int di(int a) {
	return ((a + 10) / 10) - 1;
}
int ma(int n, int a, int b, int c) {
	if (n < 0) {
		return 0;
	}
	if (n == 0) {
		if (a == 0 and b == 0 and c == 0) {
			return 1;
		}
		else {
			return 0;
		}
	}
	else {
		int e = di(n - 3);
		int f = di(n - 5);
		int g = di(n - 7);
		int x = ma(e, 0, b, c);
		int y = ma(f, a, 0, c);
		int z = ma(g, a, b, 0);
		if (a == 0 and b == 0 and c == 0) {
			return x + y + z + 1;
		}
		else {
			return x + y + z;
		}
	}
}
int main()
{
	int s,a,b,c;
	cin >> s;
	cout << ma(s,1,1,1) << endl;
	return 0;
}


Measured memory_bytes: 256
# python3.4.2用
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD
def lprint(l): print(*l, sep='\n')
def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

Q = iin()
L = []
R = []
for i in range(Q):
    l,r = imn()
    L.append(l)
    R.append(r)    

is_primes = sieves_of_e(10**5+1)

s = [0 for _ in range(10**5+1)]
for i in range(1, 10**5):
    s[i] = s[i-1]
    if i % 2 == 1:
        if is_primes[i] and is_primes[(i+1)//2]:
            s[i] = s[i-1]+1

for i in range(Q):
    print(s[R[i]] - s[L[i]-1])




Measured memory_bytes: 15796
var
 n,w,s,e,i:longint;
 a:ansistring;
begin
 read(a);
 for i:=1 to length(a) do 
  begin
   case a[i] of 
    'N':n:=1;
    'W':w:=1;
    'S':s:=1;
    'E':e:=1;
   end;
  end;
 if (n=s) and (w=e) then writeln('Yes')
  else writeln('No');
end.

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

int main() {
  long n,ans=0,p=0;
  cin >> n;
  vector<vector<long>> a(n,vector<long>(n-1));
  vector<vector<bool>> b(n,vector<bool>(n));
  vector<long> c(n);
  queue<long> x;
  queue<long> y;
  for(long i=0;i<n;i++) for(long j=0;j<n-1;j++) cin >> a[i][j];

  for(long i=0;i<n;i++) {
    b[i][a[i][0]-1]=true;
    if(b[a[i][0]-1][i]) {
      x.push(i);
      y.push(a[i][0]-1);
    }
  }

  while(p<n*(n-1)/2) {
    ans++;
    long z=x.size();
    if(z==0) break;
    for(long i=0;i<z;i++) {
      c[x.front()]++;
      c[y.front()]++;
      if(c[x.front()]!=n-1) {
        b[x.front()][a[x.front()][c[x.front()]]-1]=true;
        if(b[a[x.front()][c[x.front()]]-1][x.front()]) {
          x.push(x.front());
          y.push(a[x.front()][c[x.front()]]-1);
        }
      }
      if(c[y.front()]!=n-1) {
        b[y.front()][a[y.front()][c[y.front()]]-1]=true;
        if(b[a[y.front()][c[y.front()]]-1][y.front()]) {
          x.push(y.front());
          y.push(a[y.front()][c[y.front()]]-1);
        }
      }
      x.pop();
      y.pop();
    }
    p+=z;
  }
  
  if(p==n*(n-1)/2) cout << ans << endl;
  else cout << -1 << endl;
}

Measured memory_bytes: 8320
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
priority_queue<double,vector<double>,greater<double> > PQ;
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}

int main()
{
	int n;
	double x;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%lf",&x); PQ.push(x);
	}
	while(PQ.size()>1) 
	{
		double x=PQ.top(),y;
		PQ.pop();
		y=PQ.top();
		PQ.pop();
		PQ.push((x+y)/2.0);
	}
	printf("%lf",PQ.top());
	return 0;	
} 

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

def gcd(a, b):  
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    r = a % b
    #if r == 0:
        #return b
    return gcd(b, r)

N, S = mi()
X = li()
ans = abs(S - X[0])
for i in range(1, N):
    ans = gcd(ans, abs(S - X[i]))

print(ans)

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

using namespace std;

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

    int maxA = -1, gcdA = 0;
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        maxA = max(a, maxA);
        gcdA = __gcd(gcdA, a);
    }

    if (k % gcdA == 0 && k <= maxA) {
        cout << "POSSIBLE" << endl;
    } else {
        cout << "IMPOSSIBLE" << endl;
    }
    return 0;
}

Measured memory_bytes: 768
#include "bits/stdc++.h"
#define ALL(x) x.begin(), x.end()
#define LEN(x) (int)x.size()
#define iostreamBooster() do{ cin.tie(nullptr); ios_base::sync_with_stdio(false); }while(0)
using namespace std;
typedef int64_t i64;
typedef pair<int,int> pii;
template<class A, class B>inline bool chmax(A &a, const B &b){return b>a ? a=b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, const B &b){return b<a ? a=b,1 : 0;}
constexpr int INF = 0x3f3f3f3f;

signed main()
{

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

  int a = 1;
  for (int i = 0; i < N; ++i) {
    a = min(a*2, a+K);
  }
  cout << a << endl;
  return 0;
}



Measured memory_bytes: 256
/* Includes */
#include <stdio.h>

/* Defines */
#define DATA 50

/* Prototypes */
int CountWays(int val1, int val2);

/* Main */
int main()
{
    int cnt[DATA];
    int num_max;
    int num_sum;
    int kaisu = 0;

    for (int i = 0; i < DATA; i++) {
        scanf("%d %d", &num_max, &num_sum);

        if ((num_max == 0) && (num_sum == 0)) {
            break;
        }
        else {
            /* NOP */
        }

        cnt[i] = CountWays(num_max, num_sum);
        
        kaisu = i;
    }

    for (int i = 0; i <= kaisu; i++) {
        printf("%d\n", cnt[i]);
    }

}
/* Sub */
int CountWays(int val1, int val2)
{
    int cnt = 0;

    for (int i = 1; i <= (val1 - 2); i++) {
        for (int j = i + 1; j <= (val1 - 1); j++) {
            for (int k = j + 1; k <= val1; k++) {
                if ((i + j + k) == val2) {
                    cnt++;
                }
                else {
                    /* NOP */
                }
            }
        }
    }
    return cnt;
}


Measured memory_bytes: 2064
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(int i=a;i>=b;i--)
#define ll long long int
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int k; cin>>k;
    int n; cin>>n;
    vector<int>a(n+1); a[0]=-1;
    rep(i,1,n) cin>>a[i];
    int ans=a[n]-a[1];
    rep(i,2,n)
    {
        int j=(n-1+i)%n;
        ans=min(ans,k-a[i]+a[j]);
    }
    cout<<ans<<"\n";
    return 0;
}

Measured memory_bytes: 1024
i,f,d[5],*p;main(n){for(;i>4||~scanf("%d",p=d+i);i=++i%10,f*=!!i)n=(f^f/2^f/4)&2?51:!(d[i%5]*2&f)+49,i<5?f|=*p=9<<*p:puts(&n);}

Measured memory_bytes: 0
#include<iostream>
#include<vector>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)

int cnt=0;

#define A 0
#define O 1
#define X 2

class state{
public:
  int num[(1<<4)];
  
};
const int lim = ( 1 << 4);
int table[8][(1<<4)];
int data[8];

state parse(string &in,int &p){
  state ret;
  rep(i,lim)ret.num[i]=0;
  if ( in[p]== '('){
    p++;
    state left = parse(in,p);
    p++;//space
    state right =parse(in,p);
    p++;


    rep(i,lim){
      rep(j,lim){
	int val1=i&j,val2=i|j,val3=i^j;

	int add=left.num[i]*right.num[j];
	ret.num[val1]+=add;
	ret.num[val2]+=add;
	ret.num[val3]+=add;
      }
    }
  }else if ( in[p] <='9' && in[p] >='0'){
    int now = in[p]-'0';
    now--;
    ret.num[data[now]]=1;
    p++;
  }
  return ret;
}


main(){
  string t;
  while(getline(cin,t) && t != "END"){
    int n;
    cin>>n;
    
    int num=0;
    int p=0;
    rep(i,n){
      data[i]=0;
      int kari;
      rep(j,4)cin>>kari,data[i]|=(kari<<j);
    }
    
    state ans = parse(t,p);
    cout << ans.num[(1<<4)-1]<<endl;
    getline(cin,t);
  }
  return false;
}

  

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
typedef pair<ll, ll>P;
#define PI 3.14159265359
#define MOD 1000000007
const int MAX = 510000;
ll gcd(ll a, ll b){
    if (a % b == 0)
    {  return(b);}
    else{return(gcd(b, a % b));}
}
ll lcm(ll a, ll b)
{return a * b / gcd(a, b);}

int main(){
  int N,M;cin>>N>>M;
  char A[N][N];
  char B[M][M];
  rep(i,N){
  	rep(j,N){
    	cin>>A[i][j];
    }
  }
  rep(i,M){
  	rep(j,M){
    	cin>>B[i][j];
    }
  }
  int ans=0;
  for(int i=0;i<=N-M;i++){
  	for(int j=0;j<=N-M;j++){
      	int flag=0;
    	 rep(k,M){
  			rep(l,M){
    			if(A[k+i][l+j]!=B[k][l]){flag=1;}
    		}
  		}
    	if(flag==0){ans=1;}
    }
  }
  if(ans==1){cout<<"Yes";}
  else{cout<<"No";}
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long ll;

int read() {
	char ch;
	for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
	int x=ch-'0';
	for(ch=getchar();ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x;
}

const int N=2e5+5,M=N<<1;

int l[N<<1],r[N<<1],g[N<<1],a[N];
int n;

bool check(int mid) {
	int s=1,ok=1;
	l[1]=1,r[1]=a[1]; g[1]=1;
	fo(i,2,n)
		if (a[i]>a[i-1]) {
			l[++s]=r[s-1]+1;
			r[s]=a[i];
			g[s]=1;
		} else {
			for(;l[s]>a[i];s--);
			r[s]=a[i];
			if(g[s]==mid) {
				int u=s;
				while (g[s]==mid) {g[s]=1;--s;}
				if(s==0) {ok=0;break;}
				else {
					if(l[s]==r[s])++g[s];
					else {	
						l[++s]=r[s-1];
						--r[s-1];
						r[s]=l[s];
						g[s]=g[s-1]+1;
					}
					l[++s]=r[s-1]+1;
					r[s]=a[i];
					g[s]=1;
				}
			} else {
				if (l[s]==r[s]) ++g[s];
				else {
					l[++s]=r[s-1];
					--r[s-1];
					r[s]=l[s];
					g[s]=g[s-1]+1;
				}
			}
		}
	return ok;
}

int main() {
	n=read();
	fo(i,1,n) a[i]=read();
	int l=0,r=n;
	while (l+1<r) {
		int mid=l+r>>1;
		if (check(mid)) r=mid;
		else l=mid;
	}
	printf("%d\n",r);
	return 0;
}


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

#define MAX 100001
typedef long long ll;

ll dp[MAX];
ll height[MAX];

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

    dp[0] = 0;
    dp[1] = abs(height[1]-height[0]);
    for(int i = 2; i < MAX; i++){
        dp[i] = min(abs(height[i]-height[i-2])+dp[i-2],abs(height[i]-height[i-1])+dp[i-1]);
    }

    cout << dp[n-1] << "\n";
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <tuple>

using namespace std;
typedef long long ll;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
const int INF = 1<<29;

int main(){
    int N; cin >> N;
    int K; cin >> K;
    vector<int> A(N);
    int num;
    for(int i=0;i<N;i++){
        cin >> A[i];
        if(A[i]==1) num=i;
    }
    int ans=0;
    for(int i=1;i<N;){
        i += K-1;
        ans++;
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define SIZE 300005
#define MOD 1000000007LL
#define EPS 1e-10
#define INF 1<<29
#define LLINF 1LL<<60
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define DOWN(i,b,a) for(int i=b;i>=a;i--)
#define SET(a,c) memset(a,c,sizeof a)
#define BIT(i,j) ((i)>>(j))&1
#define ALL(o) (o).begin(), (o).end()
#define ERASE(o) (o).erase(unique((o).begin(),(o).end()), (o).end())
#define SQ(x) ((x)*(x))
using namespace std;
typedef long long ll;
typedef pair<ll,ll> Pll;
typedef pair<int, int> Pii;
typedef pair<double, double> Pdd;
typedef complex<double> dcomplex;
template<typename T> inline void priv(vector<T>a){REP(i,a.size()){cerr<<a[i]<<((i==a.size()-1)?"\n":" ");}}
ll gcd(ll a,ll b){int c=max(a,b);int d=min(a,b);return c==0||d==0?c:gcd(c%d,d);}
ll lcm(ll a,ll b){return a==0||b==0?0:a*b/gcd(a,b);}
ll modpow(ll a, ll n){ll b=1;while (n>0){if(n&1)b=b*a%MOD;a=a*a%MOD;n>>=1;}return b;}

ll N;
ll fact[100010];
ll ifact[100010];

ll modcomb(ll n, ll k){
    if(k < 0 || k > n) return 0;
    ll ans = fact[n];
    ans = ans * ifact[k] % MOD;
    ans = ans * ifact[n-k] % MOD;
    return ans;
}

int main() {
    scanf("%llu", &N);
    vector<ll> cnt(N+1, -1);
    ll a, d1, d2;
    REP(i, N) {
        scanf("%llu", &a);
        if(cnt[a] != -1) {
            d1 = min(cnt[a], ll(i));
            d2 = max(cnt[a], ll(i));
            break;
        }
        cnt[a] = i;
    }
    fact[0] = 1;
    ifact[0] = 1;
    FOR(i, 1, N+2) {
        fact[i] = fact[i-1] * i % MOD;
        ifact[i] = modpow(fact[i], MOD-2);
    }
    ll ans;
    printf("%lld\n", N);
    FOR(k, 2, N) {
        ans = modcomb(N-1, k) % MOD;
        ans = (ans + 2 * modcomb(N-1, k-1)) % MOD;        
        ans = (ans - modcomb(N-1-(d2-d1-1), k-1) + MOD) % MOD;
        ans = (ans + modcomb(N-1, k-2)) % MOD;
        printf("%llu\n", ans);
    }
    printf("1\n");
 	return 0;
}


Measured memory_bytes: 3584
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> p2;
const ll hell=4000005;
ll cnt[2005];
void solve(){
	ll n,sum=0;
	cin>>n;
	for(ll i=0;i<n;i++){
		ll x;
		cin>>x;
		sum+=x;
		cnt[x]++;
	}
	sum=(sum+1)/2;
	vector<ll> v;
	for(ll i=1;i<=2000;i++)
	if(cnt[i]){
		for(ll j=0;(1<<j)<=cnt[i];j++){
			v.push_back((1<<j)*i);
			cnt[i]-=(1<<j);
		}
		if(cnt[i])
		v.push_back(cnt[i]*i);
	}
	bitset<hell> dp;
	dp.set(0);
	for(ll i=0;i<ll(v.size());i++)
	dp|=(dp<<v[i]);
	while(sum<4000005){
		if(dp.test(sum)){
			cout<<sum;
			exit(0);
		}
		sum++;
	}
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll qc=1;
    for(ll i=1;i<=qc;i++)
    solve();
}


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

int main(){
  string S;
  cin >> S;
  
  if(S == "Sunny"){cout << "Cloudy";}
  else if(S == "Cloudy"){cout << "Rainy";}
  else if(S == "Rainy"){ cout << "Sunny";}
  
  return 0;
  
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <string>
#include <set>
#include <bitset>
#include <unordered_map>
#include <cmath>
#include <functional>
#include <map>
#include <cstdlib>

using namespace std;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
template <class T>
using Vvec = vector<vector<T> >;

template <class T>
void debug(T& v)
{
    for(auto& x: v) cout << x << " ";
    cout << endl;
}

int main()
{
    int N;
    cin >> N;
    vector<ll> a(N);
    for(auto& x: a) cin >> x;

    vector<ll> s(N+1);
    for(int i=0; i<N; i++) s[i+1] = s[i] + a[i];
    Vvec<ll> dp(N, vector<ll>(N, 1e18));
    Vvec<ll> amin(N, vector<ll>(N));

    for(int i=0; i<N; i++){
        dp[i][i] = a[i];
        amin[i][i] = i;
    }
    for(int l=1; l<N; l++){
        for(int i=0; i+l<N; i++){
            int j=i+l;
            for(int k=amin[i][j-1]; k<=amin[i+1][j]; k++){
                if(k>=j) break;
                ll n = dp[i][k] + dp[k+1][j] + s[j+1] - s[i];
                if(n < dp[i][j]){
                    dp[i][j] = n;
                    amin[i][j] = k;
                }
            }
        }
    }

    cout << dp[0][N-1] - s[N] << endl;
    // for(auto& v: amin) debug(v);
    // for(auto& v: dp) debug(v);
}

Measured memory_bytes: 2816
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 5;

int a[N], n;

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
  sort(a + 1, a + n + 1, greater <int> ());
  int i, j;
  for (i = 1; i < n && a[i + 1] >= i + 1; i ++);
  if ((a[i] - i) & 1) return !puts("First");
  if (a[i + 1] == i) {
    for (j = i + 1; j < n && a[j + 1] == i; j ++);
    if ((j - i) & 1) return !puts("First");
  }
  puts("Second");
  return 0;
}


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

using namespace std;
#define mp(a,b) make_pair(a,b)
#define fast cin.tie(0);cout.tie(0);std::ios_base::sync_with_stdio(0);
#define fuf -1;
#define YES cout << "YES\n";
#define NO cout << "NO\n";
#define min3(a,b,c) min(min(a,b),c)
#define max3(a,b,c) max(max(a,b),c)
#define mid3(a,b,c) a+b+c-max3(a,b,c)-min3(a,b,c)
#define nullptr NULL
//typedef long long int ll;
#define int long long

const double EPS = 0.0000000001;
const int mod1 = 998244353;
const int mod2 = 1000000007;
const int mod3 = 1000000009;
const int inf = 1000000000000000000;
using namespace std;

signed main(){
    int a,b;
    cin >> a >> b;
    cout << max(a,b) +  max(max(a,b)-1,min(a,b));
}


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

using namespace std;
vector<int> G;
long long cnt; 
void insertionSort(vector<int> &A,int n, int g)
{
	for(int i=g;i<n;++i)//i指向待插数的位置
	{
		int v=A[i];
		int j=i-g; //j指向A[i]要插入的位置 
		
		while(j>=0&&A[j]>v)//满足插入条件 ,如果不满足则A[i]的位置不变，i指向下一个待插数 
		{
			A[j+g]=A[j]; //此出不能用A[i]=A[j],j可能会继续往前指，j的后一位并不总是i 
			j-=g;        //A[i]并不急于放入A[j],继续再和前一个位置比较j=j-g
			cnt++; 
		 } 
		 A[j+g]=v;
	} 
	
	
}

void shellsort(vector<int> &A,int n)
{
	//初始化间隔序列 
	for(int h=1;h<=n;)
	{
		G.push_back(h); 
		h=3*h+1;
	}
	//倒叙 循环 进行插入排序
	for(int i=G.size()-1;i>=0;--i)
	{
		insertionSort(A,n,G[i]);
		
	 } 
	
}

int main()
{
	int n,a;
	vector<int> array;
	cin>>n;
	
	for(int i=0;i<n;++i)
	{
	cin>>a;
	array.push_back(a);	
	}
	//排序 
	shellsort(array,n); 
	
	//output 
	cout<<G.size()<<endl;
	for(int p=G.size()-1;p>=0;--p)
	{
		if(p==0)
		cout<<G[p]<<endl;
		else
		cout<<G[p]<<" ";
	}
		
	cout<<cnt<<endl;
	for(int i=0;i<n;++i)
	{
		cout<<array[i]<<endl;
	}
	return 0;
 } 


Measured memory_bytes: 7048
n,m = map(int,input().split())
l = [[] for i in range(n)]

for i in range(m):
    a,b = map(int,input().split())
    l[a-1].append(b-1)
    l[b-1].append(a-1)

mp = [False]*n
mcnt = 0
for i in range(n):
    if mp[i]:
        continue
    queue = [i]
    cnt = 0
    mp[i] = True
    while(queue):
        num = queue.pop()
        cnt += 1
        target = set(l[num])
        for x in target:
            if mp[x]:
                continue
            mp[x]=True
            queue.append(x)
    mcnt = max(cnt,mcnt)

print(mcnt)


Measured memory_bytes: 45232
#include<iostream>
#include<limits>
// #include<bits/stdc++.h>
#include<algorithm>
#include<vector>
#include<cmath>
#include<math.h>
#include<iomanip>  
#include<deque> 
#include<string> 
#include<string.h>
#include<map>
#include<unordered_map>
#include<utility>
#define ll long long
#define tc(t) long long t; cin >> t; while(t--)
#define V vector
#define Vp vector< pair<int,int> >
#define pb push_back
#define UM unordered_map
#define IT iterator
#define F first
#define S second
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define PQ priority_queue
#define _FI ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const ll MOD = 1e9+7;
const ll INF = INT_MAX;
const ll _INF= INT_MIN;
using namespace std;
bool flag=true;

vector<ll> SieveOfEratosthenes(int n) 
{ 
  vector<ll> result;
    bool prime[n+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (ll p=2; p*p<=n; p++) 
    { 
        if (prime[p] == true) 
        {  
            for (ll i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
  
    for (ll p=2; p<=n; p++) 
       if (prime[p]) 
          result.push_back(p);
    return result;
}



int main()
{
 _FI

string s,t;
cin>>s>>t;
int ans=0;
for(int i=0;i<s.length();i++)
{
  if(s[i]!=t[i])
  {
    ans++;
  }
}
cout<<ans<<endl;
return 0;
}
















Measured memory_bytes: 3580
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String[] num = sc.nextLine().split(" ");
		sc.close();
		int[] n = new int[4];
		for (int i = 0; i < 4; i++) {
			n[i] = Integer.parseInt(num[i]);
		}
		int start = Math.max(n[0], n[2]);
		int end = Math.min(n[1], n[3]);
		System.out.println(end > start ? end - start : 0);
	}
}

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

int main()
{
  string s;
  cin >> s;
  
  vector <int> ext(26, 0);
  for (int i = 0; i < s.size(); i++){
    int n = s.at(i) - 'a';
    ext.at(n) = 1;
  }
  int i = 0;
  while (i < 26){
    if (ext.at(i) == 0){
      printf("%c\n", 'a' + i);
      return 0;
    }
    i++;
  }
  cout << "None" << endl;
}

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

using namespace std;

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

    if (S.at(2) == S.at(3) && S.at(4) == S.at(5))
    {
        cout << "Yes" << endl;
        return 0;
    }

    cout << "No" << endl;

    return 0;
}

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


int main() {
  string s;
  cin >> s;
  vector<int> a(26, 0);
  rep(i, s.size()) {
    a[s[i] - 'a']++;
  }
  
  bool flag = false;
  rep(i, 26) {
    if (a[i] == 0) {
      char X = 'a'+i;
      cout << X << endl;
      flag = true;
      break;
    } 
  }
  
  if (!flag)
    cout << "None" << endl;
}

Measured memory_bytes: 512
H, W = map(int, input().split())

if W == 1:
    print(1)
elif H == 1:
    print(1)
else:
    ans = W * (H // 2)
    if H % 2 == 1:
        if W % 2 == 0:
            ans += W // 2
        else:
            ans += W // 2 + 1
    print(ans)


Measured memory_bytes: 9012
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<set>
#include<utility>
#include<typeinfo>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef set<int> S;
#define rep(i, n) for(int i=0; i<n; i++)
const ll MOD=1e9+7;

int main(){

	int r;
	cin >> r;
	if(r<1200){
		cout << "ABC" << endl;
	} else if(1200<=r && r<2800){
		cout << "ARC" << endl;
	} else {
		cout << "AGC" << endl;
	}
	
	return 0;
}

Measured memory_bytes: 256
//Nihal Mittal - nihal_47
//Strike First , Strike Hard , No Mercy !!
 
/**⠀⠀⠀⠀⠀⠀⣀⣤⣤⣄⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⣰⣿⣿⣿⣿⠿⠿⣿⣿⣿⣿⣿⣿⣿⣧⢀⠀⠀⠀⠀
⠀⠀⠀⣿⣿⣿⠋⠀⠀⠀⠀⠀⠙⠀⠙⣿⣿⣿⣷⢳⢀⠀⠀⠀
⠀⠀⣠⣿⣿⣿⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⢀
⠀⠀⣸⣿⣿⣿⠸⠀⠀⠀⠒⠒⠒⠐⠀⠀⢿⣿⣿⣿⣿⣿⠀⠀
⠀⣴⣿⣿⣿⡿⠀⠒⣋⣙⡒⢰⠀⠤⣖⠒⢾⣿⣿⣿⣿⣧⠀⠀
⢺⣿⣿⣿⣿⢀⠀⠀⠉⠉⠉⠸⠀⡇⠉⠉⠀⢿⣿⣿⣿⣄⠀⠀
⠀⠙⣿⣿⣧⢻⠀⠀⠀⠀⠀⠠⠀⠰⠀⠀⠀⣸⠸⣿⣿⠿⠰⠀
⠀⠀⠀⠹⣿⣿⣿⣷⠀⡠⠙⣲⣔⣅⢡⣰⣷⣿⣿⣿⣧⠀⠀⠀
⠀⠀⠀⣼⣿⣿⣿⣿⠀⡿⠭⠭⠭⠭⢿⠀⣿⢻⣿⣿⠃⠀⠀⠀
⠀⠀⠀⠙⠛⣿⢻⠹⣿⠐⠙⠛⠟⠉⢀⣴⡟⢿⣿⡏⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⡟⠀⠀⠻⣦⣤⣶⠾⠋⠀⠀⠁⡦⢄⢀⠀⠀⠀
⠀⠀⠀⠀⡠⠁⡇⠑⢄⠀⠀⠀⠀⠀⠀⠔⠀⠀⠁⠀⠀⠀⠉⠁
⠀⠔⠊⠁⠀⠀⣇⠀⠀⠀⠑⡤⠤⢎⠁⠀⠀⡘⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢢⠠⠀⡠⢆⠀⠀⡠⠙⢄⠀⡸⠀
**/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define l long
#define mk make_pair
#define pb push_back
#define in insert
#define se second
#define fi first
#define mod 1000000007
#define watch(x) cout << (#x) << " is " << (x) << "\n"
#define all(v) (v).begin(),(v).end()
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0);
#define pii pair<int,int>
#define maxn 100005
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
using namespace std;
using namespace __gnu_pbds;
ll ma[5][100005];
signed main()
{
    fast;
    
    int a,b,i;
    cin>>a>>b;
    string s1,s2;
    for(i=0;i<b;i++) s1.pb('0' + a);
    for(i=0;i<a;i++) s2.pb('0' + b);
    if(s1<s2) cout<<s1;
    else cout<<s2;
}

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

const int maxv = 1005, maxe = 2005;

int md[maxv], pt[maxv];
int q[maxv], qh = 0, qt = 0;
bool inq[maxv];
vector<pair<int, int>> G[maxv];

bool empty() { return qh == qt; }

void push(int v) {
	if (inq[v]) return;
	inq[v] = true;
	q[qt] = v;
	qt++;
	if (qt >= maxv) qt -= maxv;
}

int pop() {
	int v = q[qh++];
	inq[v] = false;
	if (qh >= maxv) qh -= maxv;
	return v;
}

int main() {
	int v, e, r; cin >> v >> e >> r;
	
	for (int i = 0; i < e; i++) {
		int s, t, d; cin >> s >> t >> d;
		G[s].push_back({t, d});
		//G[t].push_back({s, d});
	}
	
	bool ok = true;
	fill(md, md + maxv, 0x3f3f3f3f);
	
	md[r] = 0;
	push(r);
	
	while (!empty()) {
		int t = pop();
		pt[t]++;
		if (pt[t] > maxe) {
			ok = false;
			break;
		}
		for (pair<int, int> p : G[t]) {
			if (md[t] + p.second < md[p.first]) {
				md[p.first] = md[t] + p.second;
				push(p.first);
			}
		}
	}
	
	if (!ok) {
		cout << "NEGATIVE CYCLE" << endl;
	} else {
		for (int i = 0; i < v; i++) {
			if (md[i] >= 0x3f3f3f3f) {
				cout << "INF" << endl;
			} else {
				cout << md[i] << endl;
			}
		}
	}
}


Measured memory_bytes: 3144
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <numeric>

using namespace std;

unsigned long long gcd(unsigned long long a, unsigned long long b){
  if(a%b == 0){
    return b;
  } else {
    return gcd(b, a%b);
  }
}

int main(){
  int n;
  cin >> n;
  unsigned long long t[n];
  for(int i = 0; i < n; i++){
    cin >> t[i];
  }
    
  unsigned long long sec = t[0];
  for(int i = 1; i < n; i++){
    unsigned long long tmp_gcd = gcd(sec, t[i]);
    if(sec % tmp_gcd == 0){
      sec = (sec/tmp_gcd)*t[i];
    } else {
      sec = (sec*t[i]/tmp_gcd);
    }
  }
  cout << sec << endl;

  return 0;
}


Measured memory_bytes: 3620