akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void)
{
  int i,n,b;
  vector<double> v;
  cin >> n;
  
  for(i = 0; i < n; i++)
  {
    cin >> b;
    v.push_back(b);
  }
  sort(v.begin(),v.end());
  
  for(i = 0; i < n - 2; i++)
  {
    v[i + 1] = (v [i] + v[i + 1]) / 2.0;
  }
  
  cout << (v [i] + v[i + 1]) / 2.0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>    
using namespace std;
#define ll long long 
#define pi pair<int,int>
#define pb push_back
#define inf 1e16
#define mod 1000000007
#define en '\n'
int pw(int a, int b){
	int ans = 1;
	while(b){
		if(b&1)ans = (ans*a)%mod;
		a = (a*a)%mod;
		b>>=1;
	}
	return ans;
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ll n;cin>>n;
	vector<vector<pi> >v;
	for(int i = 0 ; i < n ; i ++ ){
		ll a;cin>>a;
		vector<pi>row(a);
		v.pb(row);
		for(int j = 0 ; j < a ; j ++ )cin>>v[i][j].first>>v[i][j].second;
	}
	ll counter = 0 ; 
	for(int i = 0 ; i < (1<<n) ; i ++ ){
		ll no = __builtin_popcount(i);
		bitset<15>b(i);
		bool flag = false;
		for(int j = 0 ; j < n ; j ++ ){
			if(b[j]){
				for(auto el: v[j]){
					if(b[el.first-1]!=el.second){
						flag = true;
						break;
					}
				}
				if(flag)break;
			}
		}
		if(!flag)counter=max(counter,no);
	}
	cout<<counter<<en;
	return 0 ; 
}



Measured memory_bytes: 256
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

fn main() {
    let i :Vec<i32> = read_vec();
    let (a,b) = (i[0],i[1]);
    let s_sub :String = read();
    let s:Vec<char> = s_sub.chars().collect();
    let ans = match (0..a).chain(a + 1..(a + b + 1)).all(|x| s[x as usize].is_digit(10)) && s[a as usize] == '-'  {       
        true => "Yes",
        false => "No",
    };
    println!("{}",ans);
}

Measured memory_bytes: 4352
#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;

const int N = 1e6 + 69;

ll n,m,k,x,y;

ll A[N];

vector< ll > v;

string s;

int main(){

    ios::sync_with_stdio(0);

    cin>>n>>k;

    if(n%k==0){
        cout<<n/k<<endl;
    } else {
    cout<<n/k+1<<endl;}

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int         long long
#define ld          long double
#define endl        "\n"

const int mod = 1e9+7;

inline int add(int a, int b) { int res = a + b; if(res >= mod) res -= mod;  return res; }
inline int sub(int a, int b) { int res = a - b; if(res < 0) res += mod; return res;}
inline int mul(int a, int b) { return (a * b)%mod; }

const int N = 1e3+3;
int n, m;
int fa[N];
vector<int> g[N];
int mark[N];
bool ed[N][N];

void rec(int u, int par) {
    mark[u] = 1, fa[u] = par;
    for(int v : g[u]) {
        if(mark[v]==1) {
            set<int> cyc;
            int cur = u;
            while(cur != v) {
                cyc.insert(cur);
                cur = fa[cur];
            }
            cyc.insert(cur);
            bool ok = true;
            for(int x : cyc) {
                int cnt = 0;
                for(int i=1; i<=n; i++) if(cyc.count(i)) cnt += ed[x][i];
                if(cnt > 1) {
                    ok = false;
                    break;
                }
            }
            if(ok) {
                cout << cyc.size() << endl;
                for(int x : cyc) cout << x << endl;
                exit(0);
            }
        } else {
            rec(v, u);
        }
    }
    mark[u] = 2;
}


void solve() {  
    cin >> n >> m;
    for(int i=0; i<m; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        ed[u][v] = 1;
    }
    for(int root=1; root<=n; root++) if(mark[root]==0) {
        mark[root] = 1;
        rec(root, root);
    }
    cout << -1 << endl;
}

signed main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(18);

    int T = 1;
    //cin >> T;

    while(T--) {
        solve();
    }
    return 0;
}

Measured memory_bytes: 1536
#include"bits/stdc++.h"
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
const long long mod = 1000000007;
const long long inf = 11451419198109130;
typedef pair<int, int> P;
typedef pair<P, int> PP;
typedef pair<int, PP> PPP;
struct edge { int to; int to2; int cost; };
int l[100005], r[100005];
vector<int>L,R;
int u[100005];
signed main() {
	int n; cin >> n;
	rep(i, n)cin >> l[i] >> r[i];
	sort(l, l + n);
	reverse(l, l + n);
	sort(r, r + n);
	int res = 0;
	int sum = 0;
	rep(i,n) {
		sum += 2 * l[i];
		res = max(sum, res);
		sum += -2 * r[i];
		res = max(sum, res);
	}
	sum = 0;
	rep(i, n) {
		sum += -2 * r[i];
		res = max(sum, res);
		sum += 2 * l[i];
		res = max(sum, res);
	}
	cout << res << endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <numeric>
using namespace std;
typedef long long int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

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


int main() {

  int N, M;
  cin >> N >> M;
  int l, r;
  int tmpl, tmpr;
  REP(i, M){
    cin >> l >> r;
    if (i == 0) {
      tmpl = l;
      tmpr = r;
    }else{
      tmpl = max(tmpl, l);
      tmpr = min(tmpr, r);
    }
  }
  int ans = max(0, tmpr - tmpl + 1);

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }
int main()
{
  int a,b,c,d; cin >> a >> b >> c >> d;
  int x = c - a;
  int y = d - b;
  rep(i,x) cout << 'R';
  rep(i,y) cout << 'U';
  rep(i,x) cout << 'L';
  rep(i,y) cout << 'D';
  cout << 'D';
  rep(i,x+1) cout << 'R';
  rep(i,y+1) cout << 'U';
  cout << 'L';
  cout << 'U';    
  rep(i,x+1) cout << 'L';
  rep(i,y+1) cout << 'D';
  cout << "R\n";
  return 0;
}


Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,T;
  cin>>n>>T;
  int c[n],t[n];
  for(int i=0;i<n;++i){
    cin>>c[i]>>t[i];
  }
  int mi = 1001;
  for(int i=0;i<n;++i){
    if(t[i]<=T){
      mi = min(mi,c[i]);
    }
  }
  if(mi == 1001){
    cout<<"TLE";
  }
  else{
    cout<<mi;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n, m, q;
string a[2];
set<int> s[2];
void go(int x, int y) {
	int p0 = *s[0].lower_bound(x);
	int p1 = *s[1].lower_bound(x);
	int p = min(p0, p1);
	if (x + q - y < p) {
		s[0].insert(x + q - y);
		s[1].insert(x + q - y);
		return;
	}
	int v = p;
	int t = p == p1;
	s[t ^ 1].insert(v);
	while (s[t].find(v) != s[t].end()) {
		s[t].erase(v);
		v++;
	}
	if (s[t ^ 1].find(v) != s[t ^ 1].end()) {
		s[t ^ 1].erase(v);
		go(v, y + p - x);
	} else {
		s[t].insert(v);
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m >> q >> a[0] >> a[1];
	reverse(a[0].begin(), a[0].end());
	reverse(a[1].begin(), a[1].end());
	while (a[0].size() < m) {
		a[0].push_back('0');
	}
	while (a[1].size() < n) {
		a[1].push_back('0');
	}
	s[0].insert(1e9);
	s[1].insert(1e9);
	for (int i = max(n, m) - 1; i >= 0; i--) {
		if (a[0][i] == '1' && a[1][i] == '0') {
			s[0].insert(i);
		}
		if (a[0][i] == '0' && a[1][i] == '1') {
			s[1].insert(i);
		}
		if (a[0][i] == '1' && a[1][i] == '1') {
			go(i, 0);
		}
	}
	s[0].insert(-1);
	s[1].insert(-1);
	for (int i = 0; i < 2; i++) {
		auto it = --s[i].end();
		for (int j = *--it; j >= 0; j--) {
			if (j == *it) {
				it--;
				printf("1");
			} else {
				printf("0");
			}
		}
		printf("\n");
	}
	return 0;
}

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

int main(){
    int n ,a;
    cin >> n >> a;
    while(n>=500) n-=500;
    if(a>=n) cout << "Yes" <<endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
int64_t N,P;
  cin>>N>>P;
  map<int64_t,int64_t>M;
  int64_t X=P;
  for(int64_t i=2;i*i<=P&&i<=X;i++){
  if(X%i==0){
  int64_t a=0;
    while(X%i==0){X/=i; a++;}
     a/=N;
    M[i]=a;
  
  }
  }if(X!=1)
    M[X]=(1/N);
  int64_t ans=1;
    for(auto p:M){
    auto k=p.first;
      auto v=p.second;
      ans*=powl(k,v);
    
    }cout<<ans<<endl;
  
    return 0;
}


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

int main() {
    while(true) {
        int a, b;
        char op;
        cin >> a >> op >> b;

        if(op == '?') break;
        
        if(op == '+') {
            cout << a + b << endl;
        } else if(op == '-') {
            cout << a - b << endl;
        } else if(op == '*') {
            cout << a * b << endl;
        } else {
            cout << a / b << endl;
        }
    }
}


Measured memory_bytes: 3100
#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <queue>
#include <map>
#include <algorithm>
#include <functional>
#include <string>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <tuple>
using namespace std;

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

using ll = long long int;
using pll = pair<ll, ll>;

const ll mod = static_cast<ll>(1e9) + 7;

int main()
{
    ll N, D;
    cin >> N >> D;

    ll ans = 0;

    for (ll d=0;d<N;d+=2*D+1) { ++ans; }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
s = 0
S = [0]*N
for i, a in enumerate(A):
    s += a
    S[i] = s

t = S[-1]
ans = 10**20
j = 0
k = 2
for i in range(1,N-2):
    s = S[i]
    while abs(s-2*S[j+1]  ) < abs(s-2*S[j]  ): j+=1
    while abs(t-2*S[k+1]+s) < abs(t-2*S[k]+s): k+=1
    
    v = (S[j], s-S[j], S[k]-s, t-S[k])
    ans = min(ans, max(v)-min(v))
    
    #print(i,j,k, v)
print(ans)

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

int main() {
  int N,M;
  string s[101],t[101];
  cin >> N;
  for ( int i =0; i < N; i++ ) {
    cin >> s[i];
  }
  cin >> M;
  for ( int i =0; i < M; i++ ) {
    cin >> t[i];
  }

  int cntS = 1,cntT = 0,ans = 0;

    for ( int i = 0; i < N; i++ ) {
      cntS =1,cntT = 0;
      for ( int j = i+1; j < N; j++ ) {
	if ( s[i] == s[j] ) cntS++;
      }
      for ( int k = 0; k < M; k++ ) {
	if ( s[i] == t[k] ) cntT++;
      }
      ans = max(cntS-cntT,ans);
    }

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


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

int main() {
  int n, x;
  cin>>n>>x;
  if (n == 1) {
    cout<<"Yes"<<endl;
    cout<<1<<endl;
    return 0;
  }
  if (x == 1 || x == 2*n - 1) {
    cout<<"No"<<endl;
    return 0;
  }
  if (n == 2) {
    cout<<"Yes"<<endl;
    cout<<1<<endl;
    cout<<2<<endl;
    cout<<3<<endl;
    return 0;
  }
  int a[2*n-1];
  for (int i=0; i<2*n-1; i++) a[i] = 0;
  set<int> unused;
  for (int i=0; i<2*n-1; i++) unused.insert(i+1);

  a[n-1] = x;
  unused.erase(x);
  a[n-2] = x - 1;
  unused.erase(x-1);
  a[n] = x + 1;
  unused.erase(x+1);
  if (x == 2 * n - 2) {
    a[n+1] = x - 2;
    unused.erase(x-2);
  } else {
    a[n-3] = x + 2;
    unused.erase(x+2);
  }

  int idx = 0;
  for (int i: unused) {
    while (a[idx] != 0) {
      ++idx;
    }
    a[idx] = i;
  }
  cout<<"Yes"<<endl;
  for (int i=0; i<2*n-1; i++) {
    cout<<a[i]<<endl;
  }
}

Measured memory_bytes: 11648
// package app;

import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.Stream;

public class Main {

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

        // final String S = sc.next();
        // final int A = sc.nextInt();
        // final int A = sc.nextInt();
        // final int B = sc.nextInt();
        // final int C = sc.nextInt();

        String result = "";
        for (int i = 0; i < 3; i++) {
            result += sc.next().charAt(i);
        }

        // System.out.println();
        System.out.println(result);

        // System.out.println(A <= X && A + B >= X ? "YES" : "NO");

    }
}

Measured memory_bytes: 23764
#include<iostream>
using namespace std;
int main()
{int n,m,t[1000],p[1000],x[1000],i,sum=0;
cin>>n;
for(i=1;i<=n;i++)
  {cin>>t[i];
  sum+=t[i];
  }
cin>>m;
for(i=1;i<=m;i++)
  cin>>p[i]>>x[i];
for(i=1;i<=m;i++)
  if(p[i]<=n)
    cout<<sum-t[p[i]]+x[i]<<endl;
  else
    cout<<sum<<endl;
return 0;
}

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

using namespace std;

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

    int sum = 0;
    vector<int> frames(N);
    for(int i = 0; i < N; i++){
        cin >> frames[i];
        sum += frames[i];
    }
    double average = (sum + 0.0) / N;

    double minval = 99999999;
    int idx;
    for(int i = 0; i < N; i++){
        double tmp = fabs(average - frames[i]);
        if(minval > tmp){
            idx = i;
            minval = tmp;
        }
    }

    cout << idx << endl;
}

Measured memory_bytes: 256
/* ＵＴＦ－８ */
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <array>
#include <queue>
#include <stack>
#include <algorithm>
#include <tuple>
#include <numeric>
#include <type_traits>
#include <limits>

#include <stdio.h>
#include <unistd.h>
#include <fcntl.h>
#include <string.h>

#define USE_COLORED 1

#ifdef USE_COLORED
static const char stdout_pre[]  = "\033[1m"; // bold black
static const char stderr_pre[]  = "\033[31;1m"; // bold red
static const char stdxxx_post[] = "\033[m";

// 当然ながら GCC(g++)/libstdc++ 依存
#include <ext/stdio_filebuf.h>
using stdio_filebuf = __gnu_cxx::stdio_filebuf<char>;
class colored_stdio_filebuf : public stdio_filebuf {
private:
	const char* const pre_;
	const char* const post_;

public:
	colored_stdio_filebuf(FILE* fp, const char* pre, const char* post) : stdio_filebuf(fp, std::ios_base::out), pre_(pre), post_(post)
	{
	}

protected:
	std::streamsize xsputn(const char* s, std::streamsize count) override
	{
		stdio_filebuf::xsputn(pre_, strlen(pre_));
		auto ret = stdio_filebuf::xsputn(s, count);
		stdio_filebuf::xsputn(post_, strlen(post_));
		return ret;
	}
};
#endif

int main()
{
#ifdef USE_COLORED
	if (getenv("DEBUG")) {
		std::cout.rdbuf(new colored_stdio_filebuf(stdout, stdout_pre, stdxxx_post));
		std::cerr.rdbuf(new colored_stdio_filebuf(stderr, stderr_pre, stdxxx_post));
	} else
#endif
	{
		int fd = open("/dev/null", O_WRONLY);
		dup2(fd, 2);
		close(fd);
	}
	
	std::string n;
	std::cin >> n;

	for (auto ch : n) {
		if (ch == '1') {
			std::cout << '9';
		} else if (ch == '9') {
			std::cout << '1';
		} else {
			std::cout << ch;
		}
	}
	std::cout << "\n";
}


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

using int64 = long long;
using uint64 = unsigned long long;

const int64 MOD = 1e9 + 7;

constexpr int MAX_N = 100;
int64 h[MAX_N];

int64 powMod(int64 a, int64 n)
{
    int64 res = 1;
    a = a % MOD;
    while (n > 0)
    {
        if (n % 2 == 1)
        {
            res = (res * a) % MOD;
        }
        a = (a * a) % MOD;
        n >>= 1;
    }
    return res;
}

int times = 0;

pair<int64, int64> counting(int l, int r, int offset)
{
    if (l == r)
    {
        return {1, 0};
    }

    int64 cnt1 = 1, cnt2 = 1,
          minHeight = *min_element(h + l, h + r);
    
    int rectL = l, x = 0;
    for (int i = l; i < r; i++)
    {
        if (h[i] == minHeight)
        {
            auto cres = counting(rectL, i, minHeight);

            cnt1 = (cnt1 * cres.first) % MOD;
            cnt2 = (cnt2 * (cres.first + cres.second)) % MOD;

            rectL = i + 1;
            x++;    // 上に乗っかっていない
        }
    }
    auto cres = counting(rectL, r, minHeight);

    cnt1 = (cnt1 * cres.first) % MOD;
    cnt2 = (cnt2 * (cres.first + cres.second)) % MOD;

    int height = minHeight - offset;
    cnt2 = (powMod(2, x) * cnt2 % MOD + cnt1 * ((powMod(2, height) + MOD - 2) % MOD)) % MOD;
    cnt1 = powMod(2, height) * cnt1 % MOD;

    return {cnt1, cnt2};
}

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

    int N;
    cin >> N;

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

    cout << counting(0, N, 0).second << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<set>
#include<cmath>
#include<iomanip>
#include<stack>
#include<string.h>
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define sz(a) (int)a.size()
using namespace std;

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	rep(i, n) cin >> a[i];
	sort(a.begin(), a.end());
	int ans = 0;
	rep(i, k) ans += a[i];
	cout << ans << endl;
}

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

int main(void){
    int A, B, C;
    scanf("%d %d %d", &A, &B, &C);

    int i = 1;
    int *R = (int*)malloc((B+1) * sizeof(int));

    time_t start = time(NULL);
    while(1) {
        if((i*A) % B == C) {
            printf("YES\n");
            return 0;
        }
        else {
            if(R[(i*A) % B] != 0) {
                printf("NO\n");
                return 0;
            }
            R[(i*A) % B] ++;
        }
        i++;
    }
    free(R);
    return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;
public class Main {
public static void main(String args[]) {
Scanner cro=new Scanner(System.in);
int n,a,b,c;
a=cro.nextInt();
b=cro.nextInt();
if(b/100>0) n=a*1000+b;
else if(b/10>0) n=a*100+b;
else n=a*10+b;
for(c=1;c<317&&c*c!=n;c++);
if(c==317) System.out.println("No");
else System.out.println("Yes");
}   
}

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

#define PI	3.1415926535
#define EPS	0.0000000001

int main()
{
	int n,a;
	int a1,a2;
	double h1,h2;
	while(cin >> n, n)
	{
		a1=a2=0;
		h1=h2=0;
		while(--n)
		{
			cin >> a;
			a1 += a;
			h1 += sin(a*PI/180.0);
		}
		cin >> n;
		while(--n)
		{
			cin >> a;
			a2 += a;
			h2 += sin(a*PI/180.0);
		}

		h1 += sin((360-a1)*PI/180.0);
		h2 += sin((360-a2)*PI/180.0);

		if(-EPS<h1-h2 && h1-h2<EPS)
		{
			cout << 0 << endl;
		}
		else if(h1>h2)
		{
			cout << 1 << endl;
		}
		else
		{
			cout << 2 << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<algorithm>
using namespace std;
int n;
struct P{
	long long price;
	long long rjx,rjy;
}a[10];
bool cmp(P a,P b)
{
	return a.price*a.rjy/a.rjx<b.price*b.rjy/b.rjx;
}
int main()
{
	for(int i=1;i<=4;i++)  cin>>a[i].price;
	cin>>n;
	a[1].rjx=1;a[1].rjy=4;a[2].rjx=1;a[2].rjy=2;a[3].rjx=1;a[3].rjy=1;a[4].rjx=2;a[4].rjy=1;
	sort(a+1,a+5,cmp);
	long long x=1,ans=0;
	while(n>0)
	{
		long long y=n*a[x].rjy/a[x].rjx;
		ans+=y*a[x].price;
		n-=y*a[x].rjx/a[x].rjy;
		x++;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
n,a,b,c,d=map(int,input().split())
s=str(input())

if c<d:
    if s[min(a,b)-1:d+1].count("##")==0:
        print("Yes")
    else:
        print("No")
else:
    if s[min(a,b)-1:d+1].count("##")==0:
        if s[max(a,b)-2:d+1].count("...")==0:
            print("No")
        else:
            print("Yes")
    else:
        print("No")


Measured memory_bytes: 3572
#include<iostream>
#include <algorithm>
using namespace std;
int main(){
  int a,b,c;
  cin>>a>>b>>c;
    if(a>b){
  swap(a,b);
  } 
  if(b>c){
  swap(b,c);
  } 
  if(a>b){
  swap(a,b);
  }
  cout<<a<<" "<<b<<" "<<c<<endl;
  
 return 0;
 }
  

Measured memory_bytes: 3080
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <valarray>
#include <vector>

#define EPS 1e-9
#define INF 1070000000LL
#define MOD 1000000007LL
#define fir first
#define foreach(it,X) for(__typeof((X).begin()) it=(X).begin();it!=(X).end();it++)
#define ite iterator
#define mp make_pair
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define pb push_back
#define sec second
#define sz(x) ((int)x.size())

using namespace std;

struct timer{
	time_t start;
	timer(){start=clock();}
	~timer(){cerr<<1.*(clock()-start)/CLOCKS_PER_SEC<<" secs"<<endl;}
};

typedef istringstream iss;
typedef long long ll;
typedef pair<int,int> pi;
typedef stringstream sst;
typedef vector<int> vi;

int Na,Nt,Ng,Nc,m;
string s[55];
ll term[52][17];
bool over[52];
ll dp[52][52][52][52];
int conv[128];
map<string,int> M;

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	
	conv['A']=1;
	conv['T']=2;
	conv['G']=4;
	conv['C']=8;
	cin>>Na>>Nt>>Ng>>Nc>>m;
	getline(cin,s[0]);
	rep(i,m){
		getline(cin,s[i]);
		s[i]+=" ";
		int colon=s[i].find(":");
		M[s[i].substr(0,colon)]=i;
	}
	for(int i=m-1;i>=0;i--){
		int cur=s[i].find(":")+2;
		string t="";
		while(cur<sz(s[i])){
			if(s[i][cur]==' '){
				int sig=M[t];
				rep(j,16)term[i][j] += term[sig][j];
				over[i] |= over[sig];
				t="";
				cur++;
			}else if(s[i][cur]=='['){
				cur++;
				int mask=0;
				while(s[i][cur]!=']'){
					mask |= conv[s[i][cur++]];
				}
				term[i][mask]++;
				cur+=2;
			}else{
				t+=s[i][cur];
				cur++;
			}
		}
		ll sum=0;
		rep(j,16)sum+=term[i][j];
		if(sum > Na+Nt+Ng+Nc){
			over[i]=1;
		}
	}
	ll sum=0;
	rep(i,16)sum+=term[0][i];
	if(over[0] || sum!=Na+Nt+Ng+Nc){
		cout<<0<<endl;
		return 0;
	}
	vi v;
	rep(i,16){
		rep(j,term[0][i])v.pb(i);
	}
	//rep(i,sz(v))cout<<v[i]<<" ";cout<<endl;
	dp[0][0][0][0]=1;
	rep(sum,Na+Nt+Ng+Nc)rep(i,Na+1)rep(j,Nt+1)rep(k,Ng+1){
		int l=sum-i-j-k;
		if(l>Nc)continue;
		if(v[sum]&1){
			dp[i+1][j][k][l] += dp[i][j][k][l];
			dp[i+1][j][k][l] %= MOD;
		}
		if(v[sum]&2){
			dp[i][j+1][k][l] += dp[i][j][k][l];
			dp[i][j+1][k][l] %= MOD;
		}
		if(v[sum]&4){
			dp[i][j][k+1][l] += dp[i][j][k][l];
			dp[i][j][k+1][l] %= MOD;
		}
		if(v[sum]&8){
			dp[i][j][k][l+1] += dp[i][j][k][l];
			dp[i][j][k][l+1] %= MOD;
		}
	}
	cout<<dp[Na][Nt][Ng][Nc]<<endl;
}

Measured memory_bytes: 58304
# coding: utf-8
# Your code here!
from collections import defaultdict

n=int(input())
a=[int(x) for x in input().split()]
d=defaultdict(int)
for i in a:
    d[i]+=1
#print(d)
b=[[-2,0],[-1,0]]
for i in d:
    b.append([i,d[i]])
b.sort()

ans=1
m=len(b)
for i in range(m):
    ans=max(ans,b[i][1])
    if i+1<m and b[i][0]+1==b[i+1][0]:
        ans=max(ans,b[i][1]+b[i+1][1])
    if i+2<m and b[i][0]+1==b[i+1][0] and b[i+1][0]+1==b[i+2][0]:
        ans=max(ans,b[i][1]+b[i+1][1]+b[i+2][1])
print(ans)


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

using namespace std;
typedef long long ll;
const int N=2e5+10;

int main()
{
    int n,m;
    cin>>n>>m;
    if(n%2){
        for(int i=1;i<=m;i++){
            cout<<i<<" "<<n-i<<endl;
        }
    }
    else{

            int r=n;
            for(int i=1;i<=m;i++){
                if(i==n/4+1){
                    r--;
                }
                cout<<i<<" "<<r<<endl;
                r--;
            }


        }
}



Measured memory_bytes: 3636
class Unionfind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def root (self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def connect(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def isConnect(self, x):
        return self.root(x) == self.root(y)

    def size(self, x):
        return -self.parents[self.root(x)]

def solve():
    N, K = map(int, input().split())
    P = list(map(lambda x: int(x) - 1, input().split()))
    C = list(map(int, input().split()))
    INF = 10 ** 18
    dp = [[-INF] * (N + 1) for i in range(N)]
    ans = -INF
    uf = Unionfind(N)
    for i in range(N):
        dp[i][0] = 0
        now = i
        for j in range(min(N, K)):
            now = P[now]
            uf.connect(i, now)
            dp[i][j + 1] = dp[i][j] + C[now]
            ans = max(ans, dp[i][j + 1])
    for i in range(N):
        M = uf.size(i)
        if dp[i][M] < 0:
            continue
        roop = K // M
        move = K % M
        if move == 0:
            roop -= 1
            move = M
        for j in range(move):
            ans = max(ans, dp[i][M] * roop + dp[i][j + 1])
    return ans

print(solve())


Measured memory_bytes: 271088
/**
** 
** Last Updated: 2019/09/26 17:26:50 JST
** (c) was
**/
#include <bits/stdc++.h>
using namespace std;

int main() {
  //input
  int x,a;cin >> x >> a;
  //compute
  if(x<a)
    printf("0\n");  
  else
    printf("10\n");
  return 0;
	
}


Measured memory_bytes: 256
x,y = map(int,input().split())
ans = float('inf')
if x <= y:
    ans = min(ans,y - x)
if x <= -y:
    ans = min(ans,-y-x+1)
if -x <= y:
    ans = min(ans,y + x + 1)
if -x <= -y:
    ans = min(ans,-y + x + 2)
print(ans)


Measured memory_bytes: 3060
#include "bits/stdc++.h"
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <set>
#include <tuple>
using namespace std;

#define FOR(i,init,a) for(int i=init; i<a; i++)
#define rep(i,a) FOR(i,0,a)
#define rrep(i,a) for(int i=a; i>=0; i--)
#define rep1(i,a) for(int i=1; i<=a; i++)
#define cout1(a) cout << a << endl;
#define cout2(a,b) cout << a << " " << b << endl;
#define cout3(a,b,c) cout << a << " " << b << " " << c << endl;
#define cout4(a,b,c,d) cout << a << " " << b << " " << c << " " << d << endl;
#define mem(a,n) memset( a, n, sizeof(a))
#define all(a) a.begin(),a.end()
#define chmin(a,b) a=min(a,b);
#define chmax(a,b) a=max(a,b);

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LLINF = 1e18;
static const double pi = 3.141592653589793;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N,M;
    map<int,int> dic;
    
    cin>>N;
    rep(i,N){
        int d;cin>>d;
        dic[d]++;
    }
    
    bool f=true;
    cin>>M;
    rep(i,M){
        int d; cin>>d;
        if(dic[d]<=0){
            f=false;
            break;
        }
        dic[d]--;
    }
    
    if(f) cout1("YES")
    else cout1("NO")
}

Measured memory_bytes: 9600
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
using namespace std;

int main(){
    string s;
    int N;
    cin >> N;
    vector<int> V(N);
    vector<int> C(N);
    for(int i = 0; i < N ; i++){
        cin >> V[i];
    }
    for(int i = 0; i < N ; i++){
        cin >> C[i];
    }
    int X = 0, Y = 0;
    for(int i = 0 ; i < N ;i++){
        if(V[i] > C[i]){
            X += V[i];
            Y += C[i];
        }
    }
    cout << X - Y << endl;
    return 0;
} 

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

var sc = bufio.NewScanner(os.Stdin)

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	s := strings.Split(nextLine(), "")
	k, _ := strconv.Atoi(nextLine())
	ans := ""

	if s[0] != "1" {
		ans = s[0]
	} else {
		ans = "1"
		for i := 1; i < k; i++ {
			if s[i] != "1" {
				ans = s[i]
				break
			}
		}
	}

	fmt.Println(ans)
}


Measured memory_bytes: 640
import sys
S = int(input())
xy = [map(int, input().split()) for _ in range(S)]
x, y = [list(i) for i in zip(*xy)]
count = 0

for i in range(S):
  if x[i] == y[i]:
    count += 1
    if count == 3:
      print("Yes")
      sys.exit()
    else:
      pass
  else:
    count = 0
print("No")

Measured memory_bytes: 62580
#include <stdio.h>

int max(int x, int y)
{
	return x>y?x:y;
}

int main()
{
	int n, i, j, a[3][101];
	scanf("%d", &n);
	for(i=1; i<=2; i++)
		for(j=1; j<=n; j++)
			scanf("%d", &a[i][j]);
	a[2][1]=a[2][1]+a[1][1];
	for(i=2; i<=n; i++)
	{
		a[1][i]=a[1][i]+a[1][i-1];
		a[2][i]=a[2][i]+max(a[2][i-1], a[1][i]);
	}
	printf("%d", a[2][n]);
}

Measured memory_bytes: 128
/* A Naive recursive implementation of 0-1 Knapsack problem */
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

// C++ program of a space optimized DP solution for 

  
// val[] is for storing maximum profit for each weight 
// wt[] is for storing weights 
// n number of item 
// W maximum capacity of bag 
// dp[W+1] to store final result 
ll KnapSack(ll val[], ll wt[], int n, int W) 
{ 
    // array to store final result 
    //dp[i] stores the profit with KnapSack capacity "i" 
    ll dp[W+1]; 
      
    //initially profit with 0 to W KnapSack capacity is 0 
    memset(dp, 0, sizeof(dp)); 
  
    // iterate through all items 
    for(int i=0; i < n; i++)  
        //traverse dp array from right to left 
        for(int j=W; j>=wt[i]; j--) 
            dp[j] = max(dp[j] , val[i] + dp[j-wt[i]]); 
    /*above line finds out maximum of  dp[j](excluding ith element value) 
      and val[i] + dp[j-wt[i]] (including ith element value and the 
      profit with "KnapSack capacity - ith element weight") */    
    return dp[W]; 
} 

// Driver program to test above function 
int main() 
{ 
    int n,W;
    cin>>n>>W;
    ll val[1000],wt[1000];
    for(int i=0;i<n;i++)cin>>wt[i]>>val[i];
	cout<< KnapSack( val,wt, n,W); 
	return 0; 
} 


Measured memory_bytes: 1024
#include <algorithm>
#include <array>
#include <cstddef>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <vector>

using namespace std;

void dfs(int depth, vector<int>& s, int max_num, int n)
{
    if (depth == n)
    {
        for (auto i : s)
        {
            cout << static_cast<char>(i - 1 + 'a');
        }
        cout << endl;
    }
    else
    {
        for (int i = 1; i <= max_num + 1; i++)
        {
            s.push_back(i);
            dfs(depth + 1, s, max(max_num, i), n);
            s.pop_back();
        }
    }
};

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

    vector<int> stack;
    dfs(0, stack, 0, n);
}


Measured memory_bytes: 1536
# include <iostream>
# include <vector>


using namespace std;


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

    vector<pair<int, int>> ps(n);
    int x, l;

    for (int i=0; i<n; i++) {
        cin >> x >> l;
        ps[i] = make_pair(x+l, x-l);
    }

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

    int ans = 0;
    int cur = -1001001001;

    for (auto p: ps) {
        if (cur <= p.second) {
            cur = p.first;
            ans++;
        }
    }

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



Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rng(i, a, b) for (int i = int(a); i < int(b); i++)
#define rep(i, b) rng(i, 0, b)
#define gnr(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define per(i, b) gnr(i, 0, b)
#define bg begin()
#define ed end()
#define all(x) x.bg, x.ed
#define vi vector<int>
template <class t, class u>
bool chmax(t &a, u b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class t, class u>
bool chmin(t &a, u b)
{
    if (b < a)
    {
        a = b;
        return true;
    }
    return false;
}

int main()
{
    int n, k;
    cin >> n >> k;
    rep(i, n)
    {
        int a;
        cin >> a;
    }
    if (n == k)
    {
        cout << 1 << endl;
    }
    else
    {
        cout << (n - 2) / (k - 1) + 1 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
#include<sstream>
#include<vector>
#include<stack>
#include<math.h>
#include<queue>
#include<complex>
#include<random>
#include<ctime>
#include<set>
using namespace std;


const long long int mod=1000000007;
const long long int INF=99999999999999999;



string s,t,u;
long long int N,K,A[200005],Sum[200005]={};
double res=0;
int main() {
	cout << fixed << setprecision(18);
	cin>>N>>K;
	for(int i=1;i<=N;i++){
		cin>>A[i];
		A[i]++;
	}
	for(int i=1;i<=N;i++){
		Sum[i]=Sum[i-1]+A[i];
	}
	for(int i=K;i<=N;i++){
		res=max(res,(Sum[i]-Sum[i-K])/2.0);
	}

	cout<<res<<endl;
} 

Measured memory_bytes: 3328
#include <bits/stdc++.h>
 
#define INF INT_MAX
#define MOD 1000000007
#define REP(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
 
typedef long long ll;
typedef std::pair<int,int> pii;
 
using namespace std;
 
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll n;
    cin >> n;
    vector<ll> h(n),dp(n,INF);
    REP(i,n)cin >> h[i];

    dp[0] = 0;
    dp[1] = abs(h[1] - h[0]);
    for(int i = 2;i < n;i++){
        ll pre = dp[i-1] + abs(h[i-1] - h[i]);
        ll prepre = dp[i-2] + abs(h[i-2] - h[i]);
        dp[i] = min(pre,prepre);
    }

    cout << dp[n-1] << endl;

    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1000000007;
const ll LINF=1LL<<60;
const ll INF=1<<30;
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; }

int main(){
	ll n,k;cin>>n>>k;
	vector<ll> a(n);
	for(ll i = 0; i < n; i++) {
		cin>>a[i];
		a[i]--;
	}
	vector<ll> check(n,-1);
	ll id = 0;
	for(ll i = 0; i < 2 * n; i++) {
		// cout << id << endl;
		if (check[id] != -1){
			if (k - check[id] >= 0){
				k -= check[id];
				ll x = k % (i - check[id]);
				ll ans = id;
				for(ll j = 0; j < x; j++) {
					ans = a[ans];
				}
				cout << ans + 1 << endl;
				return 0;
			}		
			else{
				int q = 0;
				for(int j = 0; j < k; j++) {
					q = a[q];
				}
				cout << q + 1<< endl;
				return 0;
			}
		}
		else{
			check[id] = i;
			id = a[id];
		}
	}
	return 0;
}

Measured memory_bytes: 6424
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        boolean flag = true;
        String s = sc.next();
        StringBuffer sb = new StringBuffer(s);
        List<String> list = new ArrayList<String>();
        while(flag){
            int m = sc.nextInt();
            
            for(int i = 0;i<m;i++){
                int h = sc.nextInt();
                sb.append(sb.substring(0, h));
//                System.out.println(sb.toString());
                sb.delete(0, h);
//                System.out.println(sb.toString());
            }
            list.add(sb.toString());
            s = sc.next();
            sb = new StringBuffer(s);
            if(s.equals("-")){
                flag = false;
                sc.close();
            }
        }
        for(String out : list){
            System.out.println(out);
        }
        
    }
}



Measured memory_bytes: 26308
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int mat[3][3];
  int q,x;
  for(int i=0;i<3;i++)
  {
    for(int j=0;j<3;j++)
    {
      cin>>mat[i][j];
    }
  }
  cin>>q;
  if(q<3) cout<<"No";
  for(int i=1;i<=q;i++)
  {
    cin>>x;
    for(int i=0;i<3;i++)
    {
      for(int j=0;j<3;j++)
      {
		if(mat[i][j]==x){
          mat[i][j]=1;
        }
      }
    }
  }
  int sum1,sum2;
  sum1=sum2=0;
  bool flag=false;
  for(int i=0;i<3;i++)
  {
    sum1=sum2=0;
    for(int j=0;j<3;j++)
    {
     sum1+=mat[i][j];
     sum2+=mat[j][i];
    }
    if(sum1==3 || sum2==3)
    {
      flag=true;
      break;
    }
  }
  if(flag) cout<<"Yes";
  else {
    sum1=sum2=0;
    sum1+=mat[0][0]+mat[1][1]+mat[2][2];
    sum2+=mat[0][2]+mat[1][1]+mat[2][0];
    if(sum1==3 || sum2==3) cout<<"Yes";
    else cout<<"No";
  }
  return 0;
}


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

using namespace std;

typedef long long ll;

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

	return 0;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
#define rep(i,n) for (int i=0;i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;

int main() {
    string a,b,c;
    cin >> a >> b >> c;
    char turn = 'a';
    int a_p=0,b_p=0,c_p=0;
    while(true){
        if(turn=='a'){
            turn = a[a_p];
            a_p++;
        } else if(turn=='b'){
            turn = b[b_p];
            b_p++;
        } else if(turn=='c'){
            turn = c[c_p];
            c_p++;
        }

        if(turn=='a'&&a_p>=a.size()) {
            cout << 'A' << endl;
            return 0;
        }
        if(turn=='b'&&b_p>=b.size()) {
            cout << 'B' << endl;
            return 0;
        }
        if(turn=='c'&&c_p>=c.size()) {
            cout << 'C' << endl;
            return 0;
        }
    } 
}

Measured memory_bytes: 256
n,m = map(int,input().split())
ac_list = [0]*n
wa_list = [0]*n
pena = 0
for i in range(m):
    p,s = input().split()
    if s == 'AC':
        if ac_list[int(p)-1] == 0:
            ac_list[int(p)-1] =1
            pena += wa_list[int(p)-1]
        
    if s == 'WA':
        if ac_list[int(p)-1] == 0:
            wa_list[int(p)-1] += 1
            
print('{0} {1}'.format(sum(ac_list) , pena))

Measured memory_bytes: 4596
use std::cmp::min;

fn read<T: std::str::FromStr>(
    stdin_lock: &mut std::io::StdinLock,
    buf: &mut Vec<u8>,
    delimiter: u8,
) -> T {
    buf.clear();
    let l = std::io::BufRead::read_until(stdin_lock, delimiter, buf).unwrap();
    buf.truncate(l - 1); // remove delimiter
    let s = unsafe { std::str::from_utf8_unchecked(&buf) };
    s.parse().unwrap_or_else(|_| panic!("read"))
}

fn main() {
    let stdin = std::io::stdin();
    let mut stdin_lock = stdin.lock();
    let mut buf: Vec<u8> = Vec::new();
    let n: usize = read(&mut stdin_lock, &mut buf, b' ');
    let k: usize = read(&mut stdin_lock, &mut buf, b'\n');
    let mut hv = vec![0i32; n];
    for i in 0..n - 1 {
        hv[i] = read(&mut stdin_lock, &mut buf, b' ');
    }
    hv[n - 1] = read(&mut stdin_lock, &mut buf, b'\n');

    let mut cv = vec![0; n];
    for i in 1..n {
        cv[i] = cv[i - 1] + (hv[i] - hv[i - 1]).abs();
        for j in 2..k + 1 {
            if i < j {
                break;
            }
            cv[i] = min(cv[i], cv[i - j] + (hv[i] - hv[i - j]).abs());
        }
    }
    println!("{}", cv[n - 1]);
}


Measured memory_bytes: 4352
while 1:
    N = int(input())
    if N == 0:break
    R = [[0 for i in range(N+1)] for i in range(N+1)]

    def dfs_max(cur, pre):
        _max = -R[cur][pre]
        for i in range(N+1):
            if R[cur][i] > 0 and i != pre:
                _max = max(_max, dfs_max(i, cur) + R[cur][i])
    #    print('max : %d' % _max)
        return _max

    total = 0
    for i in range(N-1):
        a, b, t = list(map(int, input().split()))
        R[a][b] = t
        R[b][a] = t
        total += (t * 2)

    for i in range(2, N+1):
        spam = [x for x in R[i] if x > 0]
        if(len(spam) <= 1):
            total -= (spam[0] * 2)

    print((total - dfs_max(1, 0)))

Measured memory_bytes: 6740
n=int(input())
for i in range(n):
	A=[]
	string=input()
	for j in string:
		A.append(j)
	A.sort(reverse=True)
	Max="".join(A)
	A.sort()
	Min="".join(A)
	Min=int(Min)
	Max=int(Max)
	print(Max-Min)

Measured memory_bytes: 7664
#include <bits/stdc++.h>
#define ll long long
#define rgi register int
#define rgl register long long
#define il inline

const int N = 1e5 + 10;
const ll mod = 998244353;

ll n, max_depth, ans = 1;
ll d[N], cnt[N];

il ll read() {
	rgl x = 0, f = 0, ch;
	while(!isdigit(ch = getchar())) f |= ch == '-';
	while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}

ll qmod(ll base, ll power, ll mod) {
	ll res = 1 % mod;
	while(power) {
		if(power & 1)
			res = res * base % mod;
		base = base * base % mod;
		power >>= 1;
	}
	return res;
}

int main() {
	n = read();
	for(rgl i = 1; i <= n; ++i)	{
		d[i] = read();
		cnt[d[i]]++;
		max_depth = std::max(max_depth, d[i]);
	}
	
	for(rgl i = 1; i <= max_depth; ++i) {
		ll last = cnt[i - 1];
		ll cur = cnt[i];
		
		ans *= qmod(last, cur, mod);
		ans %= mod;
	}
	
	if(d[1] == 0 && cnt[0] == 1)
		printf("%lld", ans % mod);
	else
		printf("0");
	return 0;
}


Measured memory_bytes: 1792
N,K=map(int,input().split())
h=list(map(int,input().split()))
dp = [0]*(N)
for i in range(1,N):
    dp[i] = min(dp[j] + abs(h[j] - h[i]) for j in range(max(0, i - K), i))
print(dp[N-1])

Measured memory_bytes: 20572
#include "bits/stdc++.h"
 
typedef long long ll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define debug_vec(v) cerr<<#v<<":";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
using namespace std;

// int MOD = 998244353;
int MOD = 1000000007;

signed main(){
    
    ll n,k;
    cin >> n >> k;

    vector<ll> a(n);
    rep(i,n)cin >> a[i];

    ll tento = 0;
    for(int i = 0;i < n;i++){
        for(int j = i+1;j < n;j++){
            if(a[i] > a[j])tento++;
        }
    }

    ll mini = 0;
    rep(i,n){
        rep(j,n){
            if(a[i] > a[j])mini++;
        }
    }
    cerr << tento <<  "  " << mini << endl;
    cout << (tento*k%MOD + mini*(k*(k-1)/2%MOD)%MOD)%MOD << endl;
    
    
    
    return 0;
}

// g++ -std=c++14 code1.cpp
// rm -r -f test;oj dl https://jsc2019-qual.contest.atcoder.jp/tasks/jsc2019_qual_a
// rm -r -f test;oj dl https://cf17-final-open.contest.atcoder.jp/tasks/cf17_final_a
// rm -r -f test;oj dl http://abc125.contest.atcoder.jp/tasks/abc125_a


Measured memory_bytes: 256
s = input()
n = len(s)
dp = [0]*26

for i in s:
  dp[ord(i) - ord('a')]+=1
#print(dp)
ans = 0
#重複する二つの文字分だけ減らして加える
for j in dp:
  ans += (j * (n-j))
print(ans//2+1)

Measured memory_bytes: 3500
#include <stdio.h> 
int main()
{
	int n, mini, res, r, i;
    scanf("%d%d%d", &n, &mini, &r);
	res = r - mini;
    if(r < mini) mini = r;
	for (i = 2; i < n; i++) {
        scanf("%d", &r);
        if(r - mini > res) res = r - mini;
        if(r < mini) mini = r;
	}
    printf("%d\n", res);
	return 0;
}



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

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define MOD 1000000007LL

#define rep(i, n) for(ll (i) = 0LL;(i) < (ll)(n);(i)++)
#define rep2(i, s, e) for(ll (i) = (ll)(s);(i) < (ll)(e);(i)++)
#define repi(i, n) for(ll (i) = 0LL;(i) <= (ll)(n);(i)++)
#define repi2(i, s, e) for(ll (i) = (ll)(s);(i) <= (ll)(e);(i)++)
#define per(i, n) for(ll (i) = (ll)(n) - 1LL;(i) >= 0LL;(i)--)
#define per2(i, s, e) for(ll (i) = (ll)(s) - 1LL;(i) >= (ll)(e);(i)--)
#define peri(i, n) for(ll (i) = (ll)(n);(i) >= 0LL;(i)--)
#define peri2(i, s, e) for(ll (i) = (ll)(s);(i) >= (ll)(e);(i)--)
#define iter(i, it) for(auto &(i): (it))

template<typename T, typename U> ostream& operator<<(ostream &s, const pair<T, U> m) {
    cout << "(" << m.first << ", " << m.second << ")";
    return s;
}
template<typename T, typename U> ostream& operator<<(ostream &s, const map<T, U> m) {
    ll c = 0;
    cout << "{ ";
    iter(i, m) cout << i << (c++ == m.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
    cout << "{ ";
    rep(i, v.size()) cout << v[i] << (i == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const list<T> &v) {
    ll c = 0;
    cout << "{ ";
    iter(i, v) cout << i << (c++ == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}

int main(void) {
    string X;
    ll count = 0;
    ll s = 0;
    cin >> X;
    iter(c, X) {
        if(c == 'S') s++;
        else if(s > 0) count++, s--;
    }
    cout << X.size() - 2 * count << endl;
    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#if ONLINE_JUDGE
#define DEBUG false
#else
#define DEBUG true
#endif
#define REP(i, k, n) for (int i = (int)(k); i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define rep1(i, n) REP(i, 1, n)
#define rREP(i, k, n) for (int i = (int)(n)-1; i >= k; i--)
#define rrep(i, n) rREP(i, 0, n)
#define all(x) (x).begin(),(x).end()
#define SORT(x) std::sort(all(x))
#define REV(x) std::reverse(all(x))
#define UNIQUE(x) x.erase(std::unique(all(x)), x.end());
#define MAX(x) *std::max_element(all(x))
#define MIN(x) *std::min_element(all(x))
#define LOWitr(x, n) std::lower_bound(all(x), n)
#define UPRitr(x, n) std::upper_bound(all(x), n)
#define cii(x) int x; std::cin >> x
#define cill(x) signed long long int x; std::cin >> x
#define cis(x) std::string x; std::cin >> x
#define co(x) std::cout << x << "\n"
#define pb push_back
#define mp std::make_pair
#define F first
#define S second
#define truecheck assert
#define dump(x) if(DEBUG) std::cout<<#x<<" : "<<(x)<<"\n"
template<class T>using V = std::vector<T>;
template<class T>using VV = std::vector<std::vector<T>>;
template<class T>using Q = std::queue<T>;
template<class T>using PQ = std::priority_queue<T>;
template<class T,class U>using P = std::pair<T, U>;
template<class T,class U>using M = std::map<T, U>;
template<class T,class U>using UM = std::unordered_map<T, U>;
template<class T,class U>inline bool chmax(T &a, const U &b){if (a<b){a=b;return true;}return false;}
template<class T,class U>inline bool chmin(T &a, const U &b){if (b<a){a=b;return true;}return false;}
template<class T>inline void vcin(T &v){for(auto&& i : v) std::cin >> i;}
template<class T>inline void dumpv(const T& v, std::ostream& os = std::cout){
    if(DEBUG){
        os<<"{";
        std::for_each(all(v),[&os](typename T::value_type p){os<<p<<',';});
        os<<"}\n";
    }
}
using std::cin;
using std::cout;
using std::string;
using std::min;
using std::next_permutation;
using LL = signed long long int;
const int INF = INT_MAX, MOD = 1e9 + 7;
const LL LLINF = LLONG_MAX;
const double PI = M_PI;

void Main(){
    cill(n);
    cill(s);
    V<LL> v(n);
    V<LL> dp(6060);
    vcin(v);
    dp[0]=1;
    rep(i, n){
        V<LL> ndp(6060);
        rep(j, 3030){
            ndp[j] += dp[j]*2;
            ndp[j] %= 998244353;
            ndp[j+v[i]] += dp[j];
            ndp[j+v[i]] %= 998244353;
        }
        dp = ndp;
    }
    co(dp[s]);
}

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}

Measured memory_bytes: 3784
N = int(input())
h = [int(i) for i in input().split()]+[0]

count = 0
for key in range(1, 101):
    flag = False

    for i in range(N+1):
        if h[i] >= key:
            if not flag:
                flag = True
        else:
            if flag:
                flag = False
                count += 1


print(count)

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

using namespace std;
int ans(int A,int B,int C,int K);

int main(){
	long long int A,B,C,K;
	cin >> A >> B >> C >> K;

	long long int ans;
	if(K%2 ==0){
		ans = A-B;
	}else{
		ans = B-A;
	}
	if(abs(ans) > pow(10,18)){
		cout << "Unfair" << endl;
	}else{
		cout << ans << endl;
	}

	return 0;
}


Measured memory_bytes: 256