akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

class UnionFind {
public:
    vector<int> par, rank;
    UnionFind(int n);
    int root(int a);
    bool isConnect(int a, int b);
    void connect(int a, int b);
};

inline UnionFind::UnionFind(int n) {
    par.resize(n);
    rank.resize(n);
    for(int i = 0; i < n; ++i) {
        par[i] = i;
    }
}

inline int UnionFind::root(int a) {
    if(par[a] == a) return a;
    else return par[a] = root(par[a]);
}

inline bool UnionFind::isConnect(int a, int b) {
    return root(a) == root(b);
}

inline void UnionFind::connect(int a, int b) {
    a = root(a);
    b = root(b);
    if(a == b) return;
    if(rank[a] < rank[b]) {
        par[a] = b;
    } else {
        par[b] = a;
        if(rank[a] == rank[b]) rank[a]++;
    }
}

int main() {
    int N, K, L;
    cin >> N >> K >> L;
    vector<vector<int>> G(N);
    for(int i = 0; i < K; ++i) {
        int a, b; cin >> a >> b;
        a--, b--;
        G[a].emplace_back(b);
        G[b].emplace_back(a);
    }
    UnionFind uf(N);
    for(int i = 0; i < L; ++i) {
        int a, b; cin >> a >> b;
        a--, b--;
        uf.connect(a, b);
    }
    vector<int> ans(N);
    vector<bool> visited(N);
    for(int i = 0; i < N; ++i) {
        map<int, vector<int>> ma;
        auto dfs = [&](auto &&dfs, int cur) -> void {
            visited[cur] = true;
            ma[uf.root(cur)].push_back(cur);
            for(auto &to : G[cur]) {
                if(visited[to]) continue;
                dfs(dfs, to);
            }
        };
        if(!visited[i]) dfs(dfs, i);
        for(auto &v : ma) for(auto &e : v.second) ans[e] = v.second.size();
    }
    for(auto &e : ans) cout << e << " ";
    cout << '\n';
    return 0;
}


Measured memory_bytes: 16008
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1LL << 60;

long long Con(long long a){
    return a * (a - 1) / 2;
}

int main(){
    int N;
    if(N == 1){
        cout << 0 << endl;
        return 0;
    }
    scanf("%d", &N);
    vector<long long> A(N);
    vector<long long> B(N + 1, 0);//配列Aの累積和
    
    for(int i = 0; i < N; i++){
        scanf("%lld", &A[i]);
        B[i + 1] = B[i] + A[i];
    }
    
    sort(B.begin(), B.end());//同じ数が何個あるか数えるので
    reverse(B.begin(), B.end());
    B.push_back(INF);//番兵
    
    long long ans = 0;
    long long now = B[0];
    int cnt = 1;
    
    for(int i = 1; i <= N + 1; i++){
        if(B[i] == now){//同じ数を数える
            cnt++;
        }else{//異なったら cntC2を求める(カウント < 2 のときは選べないので求めない)
            if(cnt > 1){
                ans += Con(cnt);
            }
            now = B[i];//今見ている数とカウントを更新
            cnt = 1;
        }
    }
    
    printf("%lld\n", ans);
    return 0;
}

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

using namespace std;
using ll = long long int;

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

    ll h, w;
    cin >> h >> w;
    vector<string> a(h);
    for(auto &l: a) cin >> l;

    vector<vector<ll>> d(h, vector<ll>(w));

    ll s = 0;
    for(auto &l: a)
        for(auto &c: l)
            s += c == '#';

    queue<pair<ll,ll>> q;
    d[0][0] = 1;
    q.push({0,0});
    while(!q.empty()) {
        ll i, j;
        tie(i, j) = q.front(); q.pop();
        if(i==h-1 && j==w-1 && d[i][j] == s) {
            cout << "Possible" << endl;
            return 0;
        }
        if(i+1<h && a[i+1][j] == '#' && d[i+1][j] <= d[i][j]) d[i+1][j] = d[i][j] + 1, q.push({i+1,j});
        if(j+1<w && a[i][j+1] == '#' && d[i][j+1] <= d[i][j]) d[i][j+1] = d[i][j] + 1, q.push({i,j+1});
    }
            cout << "Impossible" << endl;
            return 0;
}


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

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n, q;
  while (cin >> n >> q, n) {
    vector<string> s(n);
    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i) {
      cin >> s[i] >> a[i] >> b[i];
    }
    while (q--) {
      int x;
      cin >> x;
      [&] {
        for (int i = 0; i < n; ++i) {
          if (b[i] - a[i] < x and x <= b[i]) {
            cout << s[i] << ' ' << x + a[i] - b[i] << '\n'; 
            return;
          }
        }
        cout << "Unknown\n";
      }();
    }
  }
}



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

int main() {
 	int n,x,t; 
	cin >> n >> x >> t;
	int ans;
  int a = 0;
  int b = 0;
  int c = 0;
  

  b = n%x;
  c = n-b;
  if(b != 0)
  {
  	a = c/x + 1;
  }
  else
  {
    a = c/x;
  }
  ans  = a * t;
  
	cout << ans << endl;
}

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

int main()
{
  int N,*A;
  long int total=0;
  cin>>N;
  A=new int[N];
  for(int i=0;i<N;i++)
    cin>>A[i];
  sort(A,A+N);
  total=A[N-1];
  int i=0;
  for(i=0;i<(N-2)/2;i++)
    total+=A[N-2-i]*2;
  if(N%2==1)
    total+=A[N-2-i];
  cout<<total;
    
  
  delete[] A;
}

Measured memory_bytes: 3668
#include<stdio.h>
int main(void)
{
	char capa,capb;
	int ball[3];
	int i,j,temp;
	
	ball[0]=1;
	ball[1]=0;
	ball[2]=0;
	while(scanf(" %c,%c",&capa,&capb)!=EOF){
		if(capa=='A'){
			i=0;
		}
		else if(capa=='B'){
			i=1;
		}
		else if(capa=='C'){
			i=2;
		}
		if(capb=='A'){
			j=0;
		}
		else if(capb=='B'){
			j=1;
		}
		else if(capb=='C'){
			j=2;
		}
		temp=ball[i];
		ball[i]=ball[j];
		ball[j]=temp;
	}
	for(i=0;i<3;i++){
		if(ball[i]==1){
			if(i==0){
				printf("A\n");
				break;
			}
			if(i==1){
				printf("B\n");
				break;
			}
			if(i==2){
				printf("C\n");
				break;
			}
		}
	}
	return 0;
}

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

using namespace std;

int main() {
    int N;
    string S, T;
    cin >> N >> S >> T;
    for(int i = 0; i < N; i++) {
        cout << S.at(i) << T.at(i);
    }
    cout << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl "\n"
#define pb push_back
#define f(i,n) for(i=0;i<n;i++)
#define F(i,a,b) for(i=a;a<=b;i++)
#define arr(a,n) for( i=0;i<n;i++)cin>>a[i];
#define fi first
#define se second
#define mp make_pair
#define mod 1000000007
#define YES cout<<"YES"<<endl;
#define Yes cout<<"Yes"<<endl;
#define NO cout<<"NO"<<endl;
#define No cout<<"No"<<endl;
#define yes cout<<"yes"<<endl;
#define no cout<<"no"<<endl;
#define vi vector<ll>
#define ed end()
#define bg begin()
#define sz size()
#define ln length()
#define s() sort(a,a+n);
#define sr() sort(a,a+n,greater<ll>());
#define v()  sort(v.begin(),v.end());
#define vr() sort(v.begin(),v.end(),greater<ll>());
#define mod 1000000007
#define fast() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
ll gcd(ll a, ll b){if(!b)return a;return gcd(b, a % b);}
ll power(ll x,ll y,ll p){ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}
int main() {
    /*#ifndef ONLINE_JUDGE
        // for getting input from input.txt
        freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        freopen("output.txt", "w", stdout);
    #endif*/
        /* 
        Ofcourse it's Hard.
        It's supposed to be Hard.
        If it's easy everyone would do it.
        HARD IS WHAT MAKES IT GREAT

        YESTERDAY U SAID TOMORROW

        SLOWLY BECOMING THE PERSON I 
        SHOULD HAVE BEEN A LONG TIME AGO

        SAME TASK CAN'T BE FOUND DIFFICULT TWICE

        BTBHWSITW

        SPRH TU KAB P

        CP IS ALL ABOUT THINKING 
        YOU HAVE MUCH MORE POTENTIAL THAN U THINK

        AJIT SHIDDAT 10

        UR DAILY ROUTINE 


        */

fast();
//ll t;cin>>t;while(t--)
{
  ll n,m;
  cin>>n>>m;
    string s[n];
    for(int i=0;i<n;i++)
    {
      cin>>s[i];
      
    }
    ll a[n][m];
    memset(a,0,sizeof(a));
    for(int i=0;i<n;i++)
    {
      for(int j=0;j<m;j++)
      {
        if(s[i][j]=='#')
        {
          //a[i][j]='#;
          if(i-1>=0)
             a[i-1][j]++;

          if(j-1>=0)
            a[i][j-1]++;
          if(i+1<n&&j+1<m)
             a[i+1][j+1]++;
           if(i-1>=0&&j-1>=0)
            a[i-1][j-1]++;
          if(i-1>=0&&j+1<m)
            a[i-1][j+1]++;
          if(i+1<n&&j-1>=0)
            a[i+1][j-1]++;
          if(i+1<n)
            a[i+1][j]++;
          if(j+1<m)
            a[i][j+1]++;
   
        }
      }
    }
    for(int i=0;i<n;i++)
    {
      for(int j=0;j<m;j++)
      {
        if(s[i][j]=='#')
          cout<<"#";
        else
        cout<<a[i][j];
      }
      cout<<endl;
    }
}
return 0;
}

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

int n, m, q, s[2000][2000], ssum[2000][2000], esum[2000][2000], e2[2000][2000];
int x[200000], y[200000], x2[200000], y2[200000];
string S[2000];

void set() {
	ssum[0][0] = s[0][0];
	for (int i = 1; i < n; i++) {
		ssum[i][0] = s[i][0] + ssum[i - 1][0];
		esum[i][0] = esum[i - 1][0];
		if (s[i][0] == 1 && s[i - 1][0] == 1) {
			esum[i][0]++;
		}
	}
	for (int i = 1; i < m; i++) {
		ssum[0][i] = s[0][i] + ssum[0][i - 1];
		e2[0][i] = e2[0][i - 1];
		if (s[0][i] == 1 && s[0][i - 1] == 1) {
			e2[0][i]++;
		}
	}
	for (int i = 1; i < n; i++) {
		for (int j = 1; j < m; j++) {
			ssum[i][j] = s[i][j] + ssum[i - 1][j] + ssum[i][j - 1] - ssum[i - 1][j - 1];
			esum[i][j] = esum[i - 1][j] + esum[i][j - 1] - esum[i - 1][j - 1];
			e2[i][j] = e2[i - 1][j] + e2[i][j - 1] - e2[i - 1][j - 1];
			if (s[i][j] == 1 && s[i - 1][j] == 1) {
				esum[i][j]++;
			}
			if (s[i][j] == 1 && s[i][j - 1] == 1) {
				e2[i][j]++;
			}
		}
	}
	/*cout << endl;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << ssum[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << esum[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << e2[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;*/
}

int main() {
	cin >> n >> m >> q;
	for (int i = 0; i < n; i++) {
		cin >> S[i];
		for (int j = 0; j < m; j++) {
			if(S[i][j] == '0')s[i][j] = 0;
			else s[i][j] = 1;
		}
	}

	for (int i = 0; i < q; i++) {
		cin >> x[i] >> y[i] >> x2[i] >> y2[i];
		//cout << "a" << endl;
	}
	set();
	//cout << "b" << endl;
	for (int i = 0; i < q; i++) {
		int a = 0, b = 0, c = 0, d, e, f, ea = 0, eb = 0, ec = 0, ed = 0, ee, ef;
		int ea2 = 0, eb2 = 0, ec2 = 0, ed2 = 0, ee2, ef2;

		if (x[i] - 1 > 0 && y[i] - 1 > 0)
		{
			a = ssum[x[i] - 2][y[i] - 2];
		}
		if (x[i] - 1 > 0) {
			b = ssum[x[i] - 2][y2[i] - 1];
			eb = esum[x[i] - 2][y2[i] - 1];
			eb2 = e2[x[i] - 2][y2[i] - 1];
			ea2 = e2[x[i] - 2][y[i] - 1];
		}
		eb = esum[x[i] - 1][y2[i] - 1];
		if (y[i] - 1 > 0) {
			c = ssum[x2[i] - 1][y[i] - 2];
			ec = esum[x2[i] - 1][y[i] - 2];
			ea = esum[x[i] - 1][y[i] - 2];
		}
		ec2 = e2[x2[i] - 1][y[i] - 1];

		d = ssum[x2[i] - 1][y2[i] - 1];
		ed = esum[x2[i] - 1][y2[i] - 1];
		ed2 = e2[x2[i] - 1][y2[i] - 1];

		/*cout << "a:" << ea << " b:" << eb << endl;
		cout << "c:" << ec << " d:" << ed << endl;
		cout << endl;
		cout << "a2:" << ea2 << " b2:" << eb2 << endl;
		cout << "c2:" << ec2 << " d2:" << ed2 << endl;*/

		e = c - a;
		ee = ec - ea;
		ee2 = ec2 - ea2;
		f = d - b;
		ef = ed - eb;
		ef2 = ed2 - eb2;

		int node = f - e;
		int edge = (ef - ee)+ (ef2 - ee2);

		//cout << "node:" << node << " edge:" << edge << endl;
		cout << (node - edge) << endl;
	}
}

Measured memory_bytes: 71552
#include <iostream>

int main(int argc, const char * argv[]) {
    int n;
    std::cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    std::cout << a[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        std::cout << " " << a[i];
    }
    std::cout << std::endl;
    return 0;
}

Measured memory_bytes: 3076
def main():
    n,c,k=map(int,input().split())
    t=[]
    for i in range(n):
        ti=int(input())
        t.append(ti)
    t.sort()
    ans=0
    i=0
    while i<n:
        j=1
        while j<c and i+j<n:
            if t[i+j]>t[i]+k:
                break
            j+=1
        ans+=1
        i+=j
    print(ans)
if __name__=="__main__":
    main()

Measured memory_bytes: 7384
#include<stdio.h>
int main()
{
	int i,j,t,a[10];
	for(i=0;i<10;i++)
	{
		scanf("%d",&a[i]);
	}
	for(i=0;i<9;i++)
	{
		t=i;
		for(j=0;j<9-i;j++)
		{
			if(a[j+1]>a[j])
			{
                t=a[j];
                a[j]=a[j+1];
                a[j+1]=t;
			}
		}
	}
    for(i=0;i<3;i++)
    {
    	printf("%d",a[i]);
    	printf("\n");
	}
	return 0;
}


Measured memory_bytes: 2044
using System;
using System.Collections.Generic;
using System.Linq;

class Program {
    static int ReadInt() { return int.Parse(Console.ReadLine()); }
    static int[] ReadInts() { return Console.ReadLine().Split().Select(int.Parse).ToArray(); }
    static string[] ReadStrings() { return Console.ReadLine().Split(); }

    static void Calc_1(long sum, long x, int p, int[] xs, List<long> hs) {
        if (p == xs.Length) {
            hs.Add(sum + x);
            return;
        }

        Calc_1(sum + x, xs[p], p + 1, xs, hs);
        Calc_1(sum, 10 * x + xs[p], p + 1, xs, hs);
    }

    static long Calc(int[] xs) {
        var hs = new List<long>();
        Calc_1(0, xs[0], 1, xs, hs);
        return hs.Sum();
    }

    static void Main() {
        var s = Console.ReadLine();
        var xs = s.Select(e => e - '0').ToArray();
        Console.WriteLine(Calc(xs));
    }
}

Measured memory_bytes: 3032
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;

int main(){
    int n;
    cin >> n;
    if(n <= 999){
        cout << "ABC" << endl;
    } else {
        cout << "ABD" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#!/usr/bin/perl

my ($n) = map { $_ - 0 } split(/\s+/,<STDIN>);
my @aa = map { $_ - 0 } split(/\s+/,<STDIN>);

my @sa = sort { $b <=> $a } @aa;

my $c = $n-1;
my $t = 0;
for(my $i=0;$i<$n;$i++){
  if( $i == 0 ){
    $c --;
    $t += $sa[$i];
  } else {
    my $c1 = ($c > 1 ? 2 : 1);
    $c -= $c1;
    $t += $c1 * $sa[$i];
  }
  last if( $c <= 0 );
}

print "$t\n";


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

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
const ll oo = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
#define sz(c) ll((c).size())
#define all(c) begin(c), end(c)
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define FORD(i,a,b) for (ll i = (b)-1; i >= (a); i--)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define TR(X) ({ if(1) cerr << "TR: " << (#X) << " = " << (X) << endl; })

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	ll n; cin >> n;
	vl x(n), y(n);
	FOR(i,0,n) cin >> x[i] >> y[i];

	vl ks(n);
	iota(all(ks),0);
	sort(all(ks),[&](ll i, ll j) { return x[i] < x[j]; });
	
	ll j = 0, ymin = n+1, xmax = 0;
	vl res(n);
	FOR(i,0,n) {
		ll k = ks[i];
		ymin = min(ymin,y[k]);
		xmax = max(xmax,x[k]);

		if (ymin+xmax == n+1) {
			ll cur = i-j+1;
			while (j <= i) {
				res[ks[j++]] = cur;
			}
		}
	}
	
	FOR(i,0,n) cout << res[i] << endl;
}



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

using namespace std;

int main(){
    int N;
    cin >> N;
    vector<long long> T(N), A(N);
    for(int i = 0; i < N; i++){
        cin >> T[i] >> A[i];
    }

    long long r = T[0], s = A[0];
    long long c;
    for(int i = 1; i < N; i++){
        c = max(r/T[i]+min(1LL, r%T[i]), s/A[i]+min(1LL, s%A[i]));
        r = c * T[i];
        s = c * A[i];
    }

    cout << r+s << endl;


    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
struct Dice{
  int s[6];
  void roll(char c){
    int b=s[0];
    if (c=='E'){
      s[0]=s[3];
      s[3]=s[5];
      s[5]=s[2];
      s[2]=b;
    }else if (c=='W'){
      s[0]=s[2];
      s[2]=s[5];
      s[5]=s[3];
      s[3]=b;
    }else if (c=='N'){
      s[0]=s[1];
      s[1]=s[5];
      s[5]=s[4];
      s[4]=b;
    }else if (c=='S'){
      s[0]=s[4];
      s[4]=s[5];
      s[5]=s[1];
      s[1]=b;
    }
  }
};

int main(){
  Dice d;
  int i;
  for (i=0;i<6;i++)cin>>d.s[i];
  string str;
  cin>>str;
  for (i=0;i<str.size();i++)d.roll(str[i]);
  cout<<d.s[0]<<endl;
  return 0;
}



Measured memory_bytes: 3208
// 有點不耐煩會破壞偉大的計劃

#include <bits/stdc++.h>

#define append push_back

using namespace std;
using ll = long long;

const int N = 1e5 + 3;
const int M = 1e6 + 7;
const long long MOD = 1e9 + 7;
const long long INF = 1e14 + 9;
const int SM = 1e3 + 5;
const int logN = 22, BL = 400;
const double EPS = 1e-9, PI = acos(-1);
const int dx[] = {1, 0, 0, -1, -1, 1, -1, 1};
const int dy[] = {0, 1, -1, 0, -1, 1, 1, -1};

void debug() {
	cerr << "\n";
}
template<typename Type1, typename... Type2>
void debug(Type1 a, Type2... b) {
    cerr << a << " ";
    debug(b...);
}

int main() {
//    freopen(".in", "r", stdin);
//    freopen(".out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int a, b, c, x, ans = 0; cin >> a >> b >> c >> x;

    for(int i = 0; i <= a; i++) {
        for(int j = 0; j <= b; j++) {
            for(int k = 0; k <= c; k++) {
                ans += (i * 500 + j * 100 + k * 50 == x);
            }
        }
    }

    cout << ans;

    return 0;
}


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

// {U}{INT,LONG,LLONG}_{MAX,MIN}
#define INF         INT_MAX/3
#define LLINF       LLONG_MAX/3
#define MOD         (1000000007LL)
#define MODA(a, b)  a=((a)+(b))%MOD
#define MODP(a, b)  a=((a)*(b))%MOD
#define inc(i, l, r)   for(int i=(l);i<(r);i++)
#define dec(i, l, r)   for(int i=(r)-1;i>=(l);i--)
#define pb          push_back
#define se          second
#define fi          first
#define mset(a, b)  memset(a, b, sizeof(a))

using LL  = long long;
using G   = vector<vector<int>>;

int di[] = {0, -1, 0, 1};
int dj[] = {1, 0, -1, 0};
// }}}

int main() {
    cin.tie(0);ios::sync_with_stdio(false);
    int n;cin >> n;
    vector<int> h(n);
    inc(i, 0, n) cin >> h[i];
    int ans = 0;
    int cnt = 0;
    inc(i, 1, n){
        if(h[i-1] >= h[i]){
            cnt++;
            ans = max(ans, cnt);
        }else{
            cnt=0;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 640
"""
problem statment url: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B
"""

from __future__ import division
from sys import stdin, maxint

def knapsack(N, W, infos):
	dp = [0] * (W + 1)
	for i in range(N):
		for j in range(W, infos[i][1] - 1, -1):
			dp[j] = max(dp[j], dp[j - infos[i][1]] + infos[i][0])

	return dp[W]


if __name__ == '__main__':
    N, W = map(int, stdin.readline().strip().split())
    infos = []
    for _ in range(N):
    	v, w = map(int, stdin.readline().strip().split())
    	infos.append((v, w))
    print(knapsack(N, W, infos))

Measured memory_bytes: 7044
IDENTIFICATION DIVISION.
PROGRAM-ID. PROGRAM_ID.

DATA DIVISION.
WORKING-STORAGE SECTION.
01 N              PIC 9(10).
01 K              PIC 9(10).
01 idx            PIC 9(10).
01 ln             PIC X(599).
01 maxlen         PIC 9(10) VALUE 100 COMP.
01 cur            PIC 9(10) VALUE 1 COMP.
01 i              PIC 9(10) VALUE 1 COMP.
01 j              PIC 9(10) COMP.
01 len            PIC 9(10) COMP.
01 ans            PIC 9(10).
01 zs             PIC Z(9)9.
01 A1.
    03 A11 OCCURS 100 DEPENDING ON N.
        05 A      PIC S9(10) VALUE 1.

PROCEDURE DIVISION.
  ACCEPT ln.
  UNSTRING ln DELIMITED BY SPACE INTO N K.
  PERFORM K TIMES
      ACCEPT maxlen
      ACCEPT ln
      MOVE 1 TO cur
      PERFORM maxlen TIMES
          PERFORM VARYING j FROM cur BY 1 UNTIL ln(j:1) = SPACE
          END-PERFORM
          COMPUTE len = j - cur
          MOVE ln(cur:len) TO idx
          MOVE ZERO TO A(idx)
          COMPUTE cur = j + 1
          ADD 1 TO i
      END-PERFORM
  END-PERFORM.
  PERFORM VARYING j FROM 1 BY 1 UNTIL N < j
      ADD A(j) TO ans
  END-PERFORM.
  MOVE ans TO zs.
  DISPLAY FUNCTION TRIM(zs).
  STOP RUN.


Measured memory_bytes: 3844
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>
using namespace std;

#define inf 0x7f7f7f7f
#define maxn 100006
#define mod 1000000007
#define N 1
#define P 2


typedef long long ll;
typedef struct {
    int u, v, next, w;
} Edge;
Edge e[1];
int cnt, head[1];

inline void add(int u, int v,int w) {
    e[cnt].u = u;
    e[cnt].v = v;
    e[cnt].w = w;
    // e[cnt].f=f;
    e[cnt].next = head[u];
    head[u] = cnt++;
    e[cnt].u = v;
    e[cnt].v = u;
    e[cnt].w = w;
    //    e[cnt].f=-f;
    e[cnt].next = head[v];
    head[v] = cnt++;
}

inline void write(int x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
inline ll read() {
    ll x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
ll h,w,a,b,f[2*100005],inv[2*100005];

ll qpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
void solve(){
    f[0]=1;
    for(ll i=1;i<=h+w-2;i++){
        f[i]=(f[i-1]*i)%mod;
    }
    inv[0]=1;
    inv[h+w-2]=qpow(f[h+w-2],mod-2);
    for(int i=h+w-3;i>0;i--)
        inv[i]=inv[i+1]*(i+1)%mod;

}
ll C(ll a,ll b){
    return f[a]*inv[b]%mod*inv[a-b]%mod;
}

int main(){
    h=read(),w=read(),a=read(),b=read();
    solve();
    ll res=0;
    for(int i=1;i<=h-a;i++){
        ll t=C(i-1+b-1,i-1)*C(h-i+w-b-1,h-i)%mod;
        res=(res+t)%mod;
    }
    cout<<res<<endl;
    return 0;
}


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

int main(){
  ll n,m,x,ans=2000000;
  cin >> n >> m >> x;
  vector<ll> c(n);
  vector<vector<ll>> a(n, vector<ll>(m));
  rep(i,n){
    cin >> c.at(i);
    rep(j,m){
      cin >> a.at(i).at(j);
    }
  }
  
  rep(s,1<<n){
    ll money = 0;
    vector<ll> check(m,0);
    rep(i,n){
      if(((s>>i)&1) == 1){
        rep(j,m){
          check.at(j) += a.at(i).at(j);
        }
        money += c.at(i);
      }
    }
    ll count = 0;
    rep(j,m){
      if(check.at(j) < x){count++;}
    }
    if(count == 0){
      ans = min(ans,money);
    }
  }
  
  if(ans == 2000000){
    cout << -1 << endl;
  }
  else{
    cout << ans << endl;
  }
  
  return 0;
}


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

int main(){
    int x;
    cin >> x;
    int m = x/500;
    int n = x%500;
    int l = n/5;
    cout << ((m*1000) + (l*5)) << endl;
    return 0;
}

Measured memory_bytes: 3612
import numpy as np
N,M,K = map(int, input().split())
a = np.array([0] + list(map(int, input().split())),dtype=np.int64)
b = np.array([0] + list(map(int, input().split())),dtype=np.int64)

asum = a.cumsum()
bsum = b.cumsum()

ans = 0
for ind,i in enumerate(asum):
    if i>K:
        break
    mx = np.searchsorted(bsum, K-i ,side='right') - 1
    ans = max(ans, ind + mx,)

print(ans)





Measured memory_bytes: 54020
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase
from collections import deque
from math import *

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

def solve():
     str1 = input()
     lst = [i for i in str1]
     if str1[-1] == 's':
        lst.append('es')
        print("".join(lst))
     else:
        lst.append('s')
        print("".join(lst))
        
           
def main():
    #k = int(input())
    #tests = 1
    #tests = int(input().strip())
    #for test in range(tests):
        solve()
        
# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Measured memory_bytes: 66484
def main():
    n=int(input())
    s=input()
    cnt=0
    for i in range(1000):
        i="".join(["00",str(i)])[-3:]
        now=0
        char=i[0]
        for c in s:
            if char==c:
                if now<2:
                    now+=1
                    char=i[now]
                else:
                    cnt+=1
                    break
    print(cnt)
main()

Measured memory_bytes: 40924
#include<bits/stdc++.h>
int main(void)
{
  using namespace std;
  int m;
  cin >> m;
  
  int ans=0;
  
  for(int i=105;i<=m;i++){
    int cunt =0;
    for(int j=1;j<=i;j+=2){
      if(i%j==0){
		cunt++;
      }
    }
    if(cunt==8){
      ans++;
    }
  }
  
  cout << ans << endl;
  return 0;
  
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define INCANT cin.tie(0), cout.tie(0), ios::sync_with_stdio(false), cout << fixed << setprecision(20);
#define int long long
#define gcd __gcd
#define all(x) (x).begin(), (x).end()
const int INF = 1e18, MOD = 1e9 + 7;
template<class T>
bool chmax(T& a, T b){return (a = max(a, b)) == b;}
template<class T>
bool chmin(T& a, T b){return (a = min(a, b)) == b;}
#define _overload(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(...) _overload(__VA_ARGS__, repi, _rep)(__VA_ARGS__)
#define _rev(i, n) revi(i, n, 0)
#define revi(i, a, b) for(int i = (int)(a - 1); i >= (int)(b); i--)
#define rev(...) _overload(__VA_ARGS__, revi, _rev)(__VA_ARGS__)
#define each(i, n) for(auto&& i: n)
signed main() {
    INCANT;
    int n, a, cnt[333333] = {}, sum[333333] = {};
    vector<int> res;
    cin>>n;
    rep(i, n){
        cin>>a;
        a--;
        sum[cnt[a]]++;
        cnt[a]++;
    }
    int i = n, tmp = n;
    rep(j, 1, n + 1){
        while(tmp < i * j){
            i--;
            tmp -= sum[i];
        }
        cout<<i<<endl;
    }
}

Measured memory_bytes: 6144
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3") 
#pragma GCC optimization ("unroll-loops")
 
// #include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
using namespace __gnu_pbds;
// const ll RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
// gp_hash_table<int, int> table;
 
#define ll  long long
#define vii vector< ll >
#define pb push_back
#define pii pair<ll,ll>
#define ppi pair<pii,ll>
#define all(x) x.begin(),x.end()
#define S second
#define F first
#define ins insert
#define ld long double
#define lp(l,r) for(i=l;i<=r;++i)
 
#define lpj(l,r) for(j=l;j<=r;++j)
#define lpr(l,r) for(i=r;i>=l;--i)
#define lprj(l,r) for(j=r;j>=l;--j)
 
#define swap(a,b){ auto _t=a;a=b,b=_t;}
#define flush() cout.flush()
#define popcount __builtin_popcount
#define die() return 0;
#define sz() size() 


 
 
#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
 
#define MD          1000000007
#define M 			200011
#define LN             14
#define fftmod      998244353
#define EPS         (double)1e-10
 
long long  md=MD;
ll inf=1e18;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 
 
 
inline ll exp(ll a,ll b){if(a==0&&b==0)return 1ll;if(a==0)return 0ll;ll r=1LL;while(b>0){if(b&1){r=(r%md)*(a%md);r=(r+md)%md;}b/=2;a=(a%md)*(a%md);a=(a+md)%md;}return (r+md)%md;}
ll gcd(ll a,ll b){if(b==0)return a;if(a==0)return b;return gcd(b,a%b);}
inline ll poww(ll a,ll b){ll r=1LL;while(b>0){if(b&1)r=r*a;b/=2;a=a*a;}return (ll)r;}
 
using cd=complex<double>;
const double PI=acos(-1);
 
inline ll rand(ll l,ll r){
    return l+rng()%(r-l+1);
}

vii g[30];
vii v[30];
int main(){
 
     
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 
 
   // ifstream fin("input.txt");ofstream fout("outut.txt");
    ll t,i,j,m,n,s,z,k,p;string s1,s2;ll q;ll x,y;
    cin>>s1>>s2;
    n=s1.sz(),m=s2.sz();
    for(i=0;i<n;++i)g[s1[i]-'a'].pb(i);
    for(i=0;i<m;++i)v[s2[i]-'a'].pb(i);
    multiset<ll> a,b;
	for(i=0;i<26;++i)if(g[i].sz())a.ins(g[i].sz());
	for(i=0;i<26;++i)if(v[i].sz())b.ins(v[i].sz());
	if(a!=b){
		cout<<"No\n";
		die();
	}
	for(i=0;i<26;++i){
		if(!g[i].sz())continue;
		char id=s2[g[i][0]];
		int flg=1;
		for(j=1;j<g[i].sz();++j){
			if(id!=s2[g[i][j]])flg=0;
		}
		if(!flg){
			cout<<"No\n";die();
		}
	}
	cout<<"Yes\n";








    

}



Measured memory_bytes: 5124
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n,i,m[600000];
vector <int> v(200000);
int main(){
	cin>>n;
  	for (i=0; i<n; i++) cin>>m[i];
  	v[1] = abs(m[1]-m[0]);
  	for (i=2; i<n; i++){
    	v[i] = min(v[i-1] + abs(m[i] - m[i-1]),v[i-2] + abs(m[i] - m[i-2]) );
    }
  	cout<<v[n-1];
}

Measured memory_bytes: 3800
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
using namespace std;
typedef long long ll;
ll const INF = 1LL << 60;

int main() {
  ll H, W;
  cin >> H >> W;
  vector<string> MAP(H);
  set<pair<ll, ll>> check_set;
  for (int i = 0; i < H; i++) {
    cin >> MAP[i];
    for (int j = 0; j < W; j++) {
      if (MAP[i][j] == '#') check_set.insert({i, j});
    }
  }
  deque<pair<ll, pair<ll, ll>>> q;
  ll max_size = check_set.size();
  q.push_back({1, {0, 0}});
  while (!q.empty()) {
    ll c = q.front().first;
    ll h = q.front().second.first;
    ll w = q.front().second.second;
    q.pop_front();
    if (w == W - 1 && h == H - 1) {
      if (c == max_size) {
        cout << "Possible" << endl;
        return 0;
      }
      continue;
    }
    if (h + 1 < H && MAP[h + 1][w] == '#') {
      q.push_back({c + 1, {h + 1, w}});
    }
    if (w + 1 < W && MAP[h][w + 1] == '#') {
      q.push_back({c + 1, {h, w + 1}});
    }
  }
  cout << "Impossible" << endl;
  return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <climits>
#include <numeric>
#include <cmath>
#include <queue>
#include <sstream>

using namespace std;
typedef long long ll;

int a, b, c, n, ans = 0;
int l[8];
const int inf = 1e9;

int dfs(int x, int aa, int bb, int cc) {
  if (x == n) {
    if (aa == 0 || bb == 0 || cc == 0) {
            return inf;
    } else {
      return abs(a - aa) + abs(b - bb) + abs(c - cc) - 30;
    }
  }
  vector<int> ret(4);
  ret[0] = dfs(x + 1, aa, bb, cc);
  ret[1] = dfs(x + 1, aa + l[x], bb, cc) + 10;
  ret[2] = dfs(x + 1, aa, bb + l[x], cc) + 10;
  ret[3] = dfs(x + 1, aa, bb, cc + l[x]) + 10;
  sort(ret.begin(), ret.end());
  return ret[0];
}

int main() {
  cin >> n >> a >> b >> c;
  for (int i = 0; i < n; i++) {
    cin >> l[i];
  }
  cout << dfs(0, 0, 0, 0) << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <numeric>
#include <array>
#include <queue>
using namespace std;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define pow(x) x*x
#define ll long long
static const int MAX = 10000;
static const ll INFTY = 1e12;

// 四方向への移動ベクトル
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

// 入力
// 入力
int H, W, N;
int sx, sy, gx, gy; 
vector<vector<char>> field;
vector<vector<int>> dist;
//vector<pair<int, int>> gx, gy;
queue<pair<int, int>> que;

// 探索
void bfs(int h, int w) {

    pair<int, int> now;
    // 初期条件 (頂点 0 を初期ノードとする)
    dist[sy][sx] = 0;
    now.first = sy; 
    now.second = sx; 
    que.push(now); 

    // 八方向を探索
    while(!que.empty()){
        pair<int, int> v = que.front();
        que.pop();

        for (int i = 0; i < 4; ++i) {
            int nh = v.first + dy[i], nw = v.second + dx[i];

            // 場外アウトしたり、0 だったりはスルー
            if (nh < 0 || nh >= H || nw < 0 || nw >= W) continue;
            if (field[nh][nw] == '#') continue;
            if (dist[nh][nw] != -1) continue;

            dist[nh][nw] = dist[v.first][v.second] + 1;
            pair<int, int> nv;
            nv.first = nh; nv.second = nw;
            que.push(nv);
        }
    }    
}

int main() {
    // 入力受け取り

    int count = 0;

    cin >> H >> W;
    field.assign(H, vector<char>(W));
    dist.assign(H, vector<int>(W, -1));
    for (int h = 0; h < H; ++h) {
      for (int w = 0; w < W; ++w) {
        cin >> field[h][w];
        if( field[h][w] == '#' ) count++;
      }
    }
    sy = 0; sx = 0; gy = H-1; gx = W-1;
    
    bfs(sy, sx);

    int ans;
    if( dist[gy][gx] != -1 ){
        ans = H * W - dist[gy][gx] - count - 1;
    }else {
       ans = -1;     
    }

    cout << ans << endl;

    //REP(i, H){
    //    REP(j, W){
    //        cout << dist[i][j] << " ";
    //    } cout << endl;
    //}

}
/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
         pass System Test!
*/

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

int main() {
int a,b,x=0,y=0;
cin>>a>>b;
x=(100*a)/8;
y=10*b;
for(int i=y;i<y+10;i++)
{
    if(((8*i)/100)==a && ((10*i)/100)==b)
    {
    cout<<i;
    return 0;
    }
}
cout<<"-1";
	return 0;
}

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

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

	int rst = 0;

	for(int i = 0; i <= A; i++) {
		for(int j = 0; j <= B; j++) {
			for(int k = 0; k <= C; k++) {
				if(i * 500 + j * 100 + k * 50 == X) rst++;
			}
		}
	}

	printf("%d\n", rst);
}


Measured memory_bytes: 256
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N = I()
xy = [tuple(MI()) for _ in range(N)]
A = [sum(xy[i]) for i in range(N)]
a = max(A)-min(A)
B = []
for i in range(N):
    x,y = xy[i]
    B.append(x-y)
b = max(B)-min(B)

print(max(a,b))




Measured memory_bytes: 119580
import java.io.PrintWriter
import kotlin.math.pow

fun next() = readLine()!!
fun nextInt() = next().toInt()
fun nextLong() = next().toLong()
fun nextDouble() = next().toDouble()
fun nextList() = next().split(" ")
fun nextIntList() = nextList().map(String::toInt)
fun nextLongList() = nextList().map(String::toLong)
fun nextDoubleList() = nextList().map(String::toDouble)

val pw = PrintWriter(System.out)
fun print(s: Any = "") = pw.print(s)
fun println(s: Any = "") = pw.println(s)

fun <T> Iterable<T>.join(separator: CharSequence = ", ", prefix: CharSequence = "", postfix: CharSequence = "") = joinToString(separator, prefix, postfix)
fun <T> Array<T>.join(separator: CharSequence = ", ", prefix: CharSequence = "", postfix: CharSequence = "") = joinToString(separator, prefix, postfix)
fun Int.pow(n: Int) = pow(n.toLong())
fun Int.pow(n: Long) = toDouble().pow(n.toDouble()).toLong()
fun Long.pow(n: Int) = pow(n.toLong())
fun Long.pow(n: Long) = toDouble().pow(n.toDouble()).toLong()

fun main(args: Array<String>) {
    main()
    pw.flush()
}

fun main() {
    val (a, b, c) = nextIntList()
    println(if (a - b == b - c) "YES" else "NO")
}

Measured memory_bytes: 36560
package main

import (
	"fmt"
)

func main() {
	var N int
	fmt.Scanf("%d", &N)

	hs := make([]int, N+10)
	for i := 0; i < N; i++ {
		fmt.Scanf("%d", &hs[i])
	}

	INF := 1 << 60
	dp := make([]int, N+10)
	dp[0] = 0
	for i := 1; i < N; i++ {
		dp[i] = INF
	}

	for i := 0; i < N; i++ {
		dp[i+1] = min(dp[i+1], dp[i]+abs(hs[i]-hs[i+1]))
		dp[i+2] = min(dp[i+2], dp[i]+abs(hs[i]-hs[i+2]))
	}
	fmt.Println(dp[N-1])
}

func min(a, b int) int {
	if a < b {
		return a
	} else {
		return b
	}
}

func abs(a int) int {
	if a > 0 {
		return a
	} else {
		return -1 * a
	}
}


Measured memory_bytes: 5504
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
#include <cmath>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i=0;i < (int)(n);i++)

int main(){
  int n,k;
  cin >> n >> k;
  vector<double> e(n);
  rep(i,n){
    double ex;
    int tmp;
    cin >> tmp;
    ex=(tmp+1)/2.0;
    e[i]=ex;
  }
  double now=0.0;
  rep(i,k){
    now+=e[i];
  }
  double ans=now; 
  for (int i=k;i < n;i++){
    now-=e[i-k];
    now+=e[i];
    ans=max(ans,now);
  }
  printf("%.10f\n",ans);

  return 0; 
}

Measured memory_bytes: 1792
import sys

readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))



import math

a,b,h,m = readints()

p = math.pi

short = m*2*p/60
long = h*2*p/12 + m*2*p/12/60

deg = min(abs(short-long),2*p-abs(short-long))

ans = math.sqrt(a**2+b**2-2*a*b*math.cos(deg))

print(ans)



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

#define int long long
struct Fast { Fast(){ std::cin.tie(0); std::cout.tie(0); ios::sync_with_stdio(false); }} fast;

#define ALL(v) begin(v), end(v)
#define RALL(v) rbegin(v), rend(v)

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

#define debug(x) cerr << #x << ": " << x << endl;

const int MOD = 1e9 + 7;

signed main(void) {

  int n; cin >> n;
  vector<int> w(n);
  for (int i = 0; i < n; ++i) cin >> w[i];
  // sort(w.begin(), w.end());

  vector<int> W(n);
  for (int i = 0; i < n; ++i) {
    if (i == 0) W[i] = w[i];
    else W[i] = W[i - 1] + w[i];
  }

  int num;
  num = abs(2 * W[0] - W[n - 1]);
  for (int i = 0; i < n - 1; ++i) {
    num = min(num, abs(abs(2 * W[i] - W[n - 1])));
  }

  cout << num << endl;
  
}


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

#define ll long long
using namespace std;

ll mod = 1e9 + 7;

int main() {
    string t, d;
    cin >> t >> d;
    vector<ll> v(d.size() + 1);
    v[0] = 1;
    for (int i = 0; i < t.size(); i++) {
        for (int j = d.size() - 1; j >= 0; j--) {
            if (t[i] == d[j]) {
                v[j + 1] += v[j];
                v[j + 1] %= mod;
            }
        }
    }

    cout << v[d.size()] << endl;
    return 0;
}


Measured memory_bytes: 3204
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<map>
#include<string.h>
#include<complex>
#include<math.h>
#include<queue>
#include <functional>
#include<time.h>
#include <stack>
#include<iomanip>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define ll long long
#define llint long long int
#define reverse(v)  reverse(v.begin(), v.end());
#define Yes(ans) if(ans)cout<<"Yes"<<endl; else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl; else cout<<"NO"<<endl;
#define hei(a) vector<a>
#define whei(a) vector<vector<a>>
#define UF  UnionFind 
#define Pint pair<int,int>
#define keta(a)  fixed << setprecision(a)
constexpr auto INF = 1000000000;
constexpr auto mod = 1000000007;
//辞書順はnext_permutation( begin( v ), end( v ) );やで！
llint gcd(llint a, llint b) {
	if (b > a)swap(a, b);
	if (a % b == 0)return b;
	return gcd(b, a % b);
}
llint Tow(int n) {//2のn乗
	if (n == 0)return 1;
	llint x = Tow(n / 2);
	x %= mod;
	x *= x;
	x %= mod;
	if (n % 2 == 1)x *= 10;
	x %= mod;
	return x;
}


int main(){
	int n;
	cin >> n;
	hei(int) dp(n+1),a(n);
	rep(i, 0, n)cin >> a[i];
	dp[0] = 0;
	dp[1] = abs(a[0] - a[1]);
	for (int i = 2; i < n; i++) {
		dp[i] = min(dp[i - 2] + abs(a[i] - a[i - 2]), dp[i - 1] + abs(a[i] - a[i - 1]));
	}
	cout << dp[n - 1] << endl;
	return 0;
}

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

main(){
	int k,r,l,a;
	vector<int> v[30];
	string s,t;
	
	cin>>s>>t;
	r = l = 0;
	
	for(int i=0;i<s.length();i++)
		v[s[i]-97].push_back(i);
		
	for(int i=0;i<t.length();i++){
		k = t[i]-97;
		if(v[k].size() == 0){
			cout<<-1;
			return 0;
		}
		a = lower_bound(v[k].begin(),v[k].end(),l) - v[k].begin();
		if(a == v[k].size()){
			r++;
			l = v[k][0]+1;
		}
		else
			l = v[k][a]+1;
	}
	cout<<r*s.length()+l;
}

Measured memory_bytes: 1216
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <numeric>
#include <iomanip>

#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
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; }

#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 998244353; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;
struct INIT { INIT(){
  cin.tie(0); ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
}}INIT;

template <typename Tu>
static inline constexpr bool is_multiplication_safe(Tu a, Tu b)
{
    return !a || b <= std::numeric_limits<Tu>::max() / a;
}

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

  vector<int> A(N);
  REP(i, N) cin >> A[i];

  REP(i, N){
    if(A[i] == 0){
      cout << 0 << "\n";
      return 0;
    }
  }

  int ans = 1;
  REP(i, N){
    if(!is_multiplication_safe(ans, A[i])){
      cout << -1 << "\n";
      return 0;
    }
    ans *= A[i];
  }

  if(ans <= 1000000000000000000ll){
    cout << ans << "\n";
  }else{
    cout << -1 << "\n";
  }

  return 0;
}

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

#define int long long
using namespace std;
#define rep(i, n) for(int i=0;i<(n);++i)
typedef pair<int, int> pii;
const int INF = 1l << 60;
#define u_b upper_bound
#define l_b lower_bound


signed main() {
    int k, x;
    cin >> k >> x;
    for (int i = -k + 1; i <= k - 1; ++i) {
        if (i != -k + 1)cout << " ";
        cout << i + x;
    }
    cout << endl;
    return 0;
}


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

int n;
vector<int> a;
vector<int> b;
vector<int> c;
vector<vector<int>> DP;

int main()
{
	cin >> n ;
	a.resize(n + 1); b.resize(n + 1); c.resize(n + 1);
	for (int i = 1; i < n + 1; i++)
		cin >> a[i]>> b[i]>>c[i];

	// max happyniess achieveable from ith day when performing a/b/c task on the day
	DP.resize(n + 1);
	for (int i = 1; i < n + 1; i++)
		DP[i].resize(3);

	// can reach n, n+1; DP[n] = 0
	DP[n][0] = a[n];
	DP[n][1] = b[n];
	DP[n][2] = c[n];
	for (int i = n - 1; i >= 1; i--)
	{
		int mc = 1000000007;
		for (int j = 0; j < 3; j++)
		{
			//find the min cost for different jumps
			if (j == 0)
				DP[i][j] = max(DP[i + 1][1], DP[i + 1][2]) + a[i];
			if (j == 1)
				DP[i][j] = max(DP[i + 1][0], DP[i + 1][2]) + b[i];
			if (j == 2)
				DP[i][j] = max(DP[i + 1][0], DP[i + 1][1]) + c[i];
		}
	}
	cout << max(DP[1][0], max(DP[1][1], DP[1][2])) << endl;
}

Measured memory_bytes: 9772
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
using namespace std;
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v;}
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str();}
typedef vector<int> vi;
typedef vector<vi>  vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EACH(t,i,c) for(t::iretator i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i,0,(n)-1)
const double EPS = 1e-12;
const double PI = acos(-1.0);

int main() {
	FOR(i, 1, 9) {
		FOR(j, 1, 9) {
			cout << i << 'x' << j << '=' << i*j << endl; 
		}
	}

	return 0;
}

Measured memory_bytes: 1116