akhauriyash/Code-Regression huggingface dataset:
import sys

INF = 10 ** 18
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict


def li():
    return [int(x) for x in input().split()]


from collections import deque

H, W = li()
Ch, Cw = li()
Dh, Dw = li()
S = [list(input()) for x in range(H)]

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def bfs():
    costmap = [[-1] * W for i in range(H)]
    costmap[Ch - 1][Cw - 1] = 0
    que = deque([])
    que.append((Cw - 1, Ch - 1))

    while que:
        # print(que)
        # 左から取り出す
        x, y = que.popleft()
        # 通常移動パターン
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # バリデーション
            if nx < 0 or nx >= W or ny < 0 or ny >= H:
                continue
            if S[ny][nx] != '.':
                continue
            # 初探索 or コストが下がる場合
            if costmap[ny][nx] == -1 or costmap[y][x] < costmap[ny][nx]:
                # コストゼロは左から
                que.appendleft((nx, ny))
                costmap[ny][nx] = costmap[y][x]
        # 特殊移動パターン
        for i in range(x - 2, x + 3):
            for j in range(y - 2, y + 3):
                nx, ny = i, j
                # バリデーション
                if nx < 0 or nx >= W or ny < 0 or ny >= H:
                    continue
                if S[ny][nx] != '.':
                    continue
                # 初探索 or コストが下がる場合
                if costmap[ny][nx] == -1 or costmap[y][x] + 1 < costmap[ny][nx]:
                    # コスト1は右から
                    que.append((nx, ny))
                    costmap[ny][nx] = costmap[y][x] + 1
    return costmap


costmap = bfs()
# print(costmap)
print(costmap[Dh - 1][Dw - 1])

Measured memory_bytes: 130448
#include<bits/stdc++.h>
using namespace std;
int a,b,c,x,y;

int main()
{
	cin>>a>>b>>c>>x>>y;
	int ans=a*x+b*y,a1=x,b1=y,c1=0;
    while (1)
        {        	
		    int ans1=ans+2*c;
			if (a1>0) {a1--;ans1-=a;}
			if (b1>0) {b1--;ans1-=b;}
			if (a1==0&&b1==0) {if (ans1<ans) ans=ans1;break; } 
        	if (ans1>=ans) break;
        	ans=ans1;
		}
	cout<<ans;
	return 0;
}

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

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a); i > (b); i--)
#define ALL(a) (a).begin(), (a).end()

int main() {
    int N, M, H[100000];
    cin >> N >> M;
    REP(i, N) cin >> H[i];

    vector<int> G[100000];
    REP(i, M) {
        int A, B;
        cin >> A >> B; A--; B--;
        G[A].push_back(B);
        G[B].push_back(A);
    }

    int ans = 0;
    REP(i, N) {
        bool ok = true;
        for (int j : G[i]) {
            if (H[i] <= H[j]) {
                ok = false;
                break;
            }
        }
        if (ok) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 9152
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <complex>
using namespace std;
#define INF 100000000

typedef long long ll;
typedef complex<double> xy_t;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

xy_t P[110];
double cross_product(xy_t a, xy_t b) {return (conj(a)*b).imag();}

int main(void) {
    int N;
    cin >> N;
    double x, y;
    for (int i = 0; i < N; i++) {
        scanf("%lf %lf", &x, &y);
        P[i] = xy_t(x, y);
    }
    double sum = 0.0;
    for (int i = 0; i+2 < N; i++) {
        xy_t a = P[0], b = P[(i+1)%N], c = P[(i+2)%N];
        xy_t x = b-a, y = c-a;
        sum += cross_product(x, y);
    }
    printf("%.1lf\n", abs(sum) / 2);
    return 0;
}

Measured memory_bytes: 1268
#include<bits/stdc++.h>
using namespace std;
int n,p[9],fact[8]={1,1,2,6,24,120,720,5040};
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&p[i]);
	for(int i=1;i<=n;i++)
	{
		p[0]+=(p[i]-1)*fact[n-i];
		for(int j=i+1;j<=n;j++)
			if(p[j]>p[i])
				p[j]--;
	}
	for(int i=1;i<=n;i++)
		scanf("%d",&p[i]);
	for(int i=1;i<=n;i++)
	{
		p[0]-=(p[i]-1)*fact[n-i];
		for(int j=i+1;j<=n;j++)
			if(p[j]>p[i])
				p[j]--;
	}
	printf("%d\n",abs(p[0]));
	return 0;
}

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

int main()
{
    int n, k;
    cin >> n >> k;
    int r, s, p;
    cin >> r >> s >> p;
    string t; 
    cin >> t;
    int ans = 0;
    vector<char> hand;
    for(int i=0; i<k; i++) {
        if(t[i] == 'r') {hand.push_back('p'); ans += p;}
        else if(t[i] == 's') {hand.push_back('r'); ans += r;}
        else if(t[i] == 'p') {hand.push_back('s'); ans += s;}
        }
    for(int i=k; i<n; i++){
        if(t[i] == 'r'){
            if(hand[i-k] == 'p') hand.push_back('#');
            else {hand.push_back('p'); ans += p;}
        } 
        else if(t[i] == 's'){
            if(hand[i-k] == 'r') hand.push_back('#');
            else {hand.push_back('r'); ans += r;}
        } 
        else if(t[i] == 'p'){
            if(hand[i-k] == 's') hand.push_back('#');
            else {hand.push_back('s'); ans += s;}
        }
    }

    cout << ans << endl;
    return 0;

}

Measured memory_bytes: 3828
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vi64 = vector<int64_t>;
using vvi64 = vector<vi64>;
#define rep(i, n) for (int64_t i = 0; i < (n); ++i)
#define repe(i, n) for (int64_t i = 0; i <= (n); ++i)
#define reps(i, s, n) for (int64_t i = (s); i < (n); ++i)
#define repse(i, s, n) for (int64_t i = (s); i <= (n); ++i)
#define repr(i, n) for (int64_t i = (n); i >= 0; --i)
#define all(xs) (xs).begin(), (xs).end()
#define pp_vec(xs) rep (i, (xs).size()) if { (i) cout << endl; cout << (xs)[i] << " "; };
const int64_t inf = (int64_t)1e18;
const int64_t mod = (int64_t)1e9 + 7;


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

  int r, D, x; cin >> r >> D >> x;

  rep (i, 10) {
    cout << r * x - D << endl;
    x = r * x - D;
  }

  return 0;
}

Measured memory_bytes: 256
#include<iostream>
    #include<vector>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    bool be[31] = {0};
    bool sg[3001] = {0};
    int main()
    {
    	int a,b,c,d,e,f;
    	scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);
    	int t;
    	be[0] = 1;
    	for(t=a;t<31;t++)
    	{
    		if(be[t-a] == 1)
    			be[t] = 1;
    	}
    	for(t=b;t<31;t++)
    	{
    		if(be[t-b] == 1)
    			be[t] = 1;
    	}
    	sg[0] = 1;
    	for(t=c;t<3001;t++)
    	{
    		if(sg[t-c] == 1)
    			sg[t] = 1;
    	}
    	for(t=d;t<3001;t++)
    	{
    		if(sg[t-d] == 1)
    			sg[t] = 1;
    	}
    	int mw=a,ms=0;
    	double ma=0;
    	for(t=f/100;t>0;t--)
    	{
    		if(be[t] == 1)
    		{
    			int sm;
    			sm = t*e;
    			if(sm > f-t*100)
    				sm = f-t*100;
    			while(sg[sm] == 0)
    				sm--;
    			if(ma < 100.0*sm/(t*100+sm))
    			{
    				ma = 100.0*sm/(t*100+sm);
    				mw = t;
    				ms = sm;
    			}
    		}
    	}
    	printf("%d %d\n",mw*100+ms,ms);
    	return 0;
    }

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

int main(){
 ll a,b,c,n,m;
 
 while(1)
 {
     cin>>n;
     if(n == 0)break;
     string leg[200];
     for(int i=0;i<n;i++)
     {
         cin>>leg[i];
     }
     for(int i=n;i<199;i++)
     {
         leg[i] == "";
     }
     int count = 0;
     bool flag[4];
     for(int i=0;i<n;i = i+2)
     {
         if((leg[i] == "lu" && leg[i+1] == "ru") || (leg[i] == "ld" && leg[i+1] == "rd") || (leg[i] == "ru" && leg[i+1] == "lu") || (leg[i] == "rd" && leg[i+1] == "ld"))
         count++;
     }
     cout<<count<<endl;
 }
}


Measured memory_bytes: 3092
using System;

namespace ABC071D
{
    class Program
    {
        static readonly int PREV_LAND = 1;
        static readonly int PREV_PORT = 2;
        static readonly int MOD = 1000000007;

        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            string S1 = Console.ReadLine();
            string S2 = Console.ReadLine();

            long res;
            int cur, prev;
            
            if(S1[0] == S2[0])
            {
                res = 3;
                cur = 1;
                prev = PREV_PORT;
            }
            else
            {
                res = 6;
                cur = 2;
                prev = PREV_LAND;
            }

            while (cur < N)
            {
                if (prev == PREV_PORT)
                {
                    if (S1[cur] == S2[cur])
                    {
                        res = (res * 2) % MOD;
                        cur += 1;
                        prev = PREV_PORT;
                    }
                    else
                    {
                        res = (res * 2) % MOD;
                        cur += 2;
                        prev = PREV_LAND;
                    }
                }
                else if (prev == PREV_LAND)
                {
                    if (S1[cur] == S2[cur])
                    {
                        // res = (res * 1) % MOD;
                        cur += 1;
                        prev = PREV_PORT;
                    }
                    else
                    {
                        res = (res * 3) % MOD;
                        cur += 2;
                        prev = PREV_LAND;
                    }
                }
                else
                {
                    throw new Exception();
                }
            }

            Console.WriteLine(res);
        }
    }
}


Measured memory_bytes: 13140
N = int(input())
d = list(map(int,input().split()))
amount = 0
b = [0] * N
for i in range(N):
    b[i] = amount
    amount += d[N-1-i]


ans = 0
for i in range(N):
    ans += d[i]*b[N-1-i]
print(ans)

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

int n, pos;
vector<int> pre, in, post;

void reconstruction(int l, int r){
  if ( l >= r){return ;}
  int root = pre[pos++];
  int m = distance(in.begin(), find(in.begin(), in.end(), root));
  reconstruction(l, m);
  reconstruction(m + 1, r);

  post.push_back(root);
}

void solve() {
  pos = 0;
  reconstruction(0, n);
  for ( int i = 0; i < n; i++){
    if (i) { cout << " ";}
    cout << post[i];
  }
  cout << endl;
}

int main(){
  cin >> n;

  int tmp;
  for ( int i = 0; i < n; i++){ cin >> tmp; pre.push_back(tmp); }
  for ( int i = 0; i < n; i++){ cin >> tmp; in.push_back(tmp); }

  solve();

  return 0;
}


Measured memory_bytes: 3164
import java.util.Scanner;

public class Main {

	/**
	 * @param args
	 */
	public static final int UP = 0;
	public static final int RIGHT = 1;
	public static final int INF = Integer.MAX_VALUE;

	public static void main(String[] args) {
		doIt();
	}

	public static void doIt(){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();

		for(int i = 0; i < n; i++){
			int gx = sc.nextInt();
			int gy = sc.nextInt();
			int p = sc.nextInt();
			boolean[][][] isM = new boolean[gx + 1][gy + 1][2];
			//またたびを撒く
			for(int j = 0; j < p; j++){
				int[][] point = new int[2][2];
				point[0][0] = sc.nextInt();
				point[0][1] = sc.nextInt();
				point[1][0] = sc.nextInt();
				point[1][1] = sc.nextInt();
				int from = 0,to = 0;
				if(point[0][0] < point[1][0] || point[0][1] < point[1][1]){
					to = 1;
				}
				else{
					from = 1;
				}
				isM[point[from][0]][point[from][1]][point[from][0] < point[to][0]? RIGHT : UP] = true;
			}
			int[][] dp = new int[gx + 1][gy + 1];
			dp[0][0] = 1;
			//一番左だけやる
			for(int j = 1; j < gy + 1; j++){
				//下から来る場合
				if(isM[0][j - 1][UP] == false){
					dp[0][j] = dp[0][j - 1];
				}
				else{
					dp[0][j] = INF;
				}
			}
			for(int j = 1; j < gx + 1; j++){
				for(int k = 0; k < gy + 1; k++){
					boolean bOK = false;
					//左から来る場合
					if(0 <= j - 1 && isM[j - 1][k][RIGHT] == false && dp[j - 1][k] < INF){
						dp[j][k] += dp[j - 1][k];
						bOK = true;
					}
					//下から来る場合
					if(0 <= k - 1 && isM[j][k - 1][UP] == false && dp[j][k - 1] < INF){
						dp[j][k] += dp[j][k - 1];
						bOK = true;
					}
					if(bOK == false){
						dp[j][k] = INF;
					}
				}
			}
			//print(dp);
			if(dp[gx][gy] == INF){
				System.out.println("Miserable Hokusai!");
			}
			else{
				System.out.println(dp[gx][gy]);
			}
		}
	}

	public static void print(int[][] a){
		for(int[] n : a){
			for(int l : n){
				System.out.print(l + " ");
			}
			System.out.println();
		}
	}

}

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

typedef long long LL;

int t, n,a,b,c;

/*
 5
 4 10 6 3
 6 5 4 3
 1 1 0 0
 31415 92653 58979 32384
 1000000000 1000000000 999999999 999999999
 */

LL floor_sum(int a,int b,int c,int n){
    if(n==0) return 0;
    LL ret = 0;
    ret += a/c * (1LL*n*(n-1)/2);
    ret += b/c * n;
    
    return ret + floor_sum(c, (1LL*a*n+b)%c, a%c, ((1LL*(a%c)*n) + b%c)/c);
}

int main() {
    cin>>t;
    while(t--){
        cin>>n>>c>>a>>b;
        cout<<floor_sum(a, b, c, n)<<endl;
    }
    
    return 0;
}


Measured memory_bytes: 3224
package main

import (
	"bufio"
	"fmt"
	"os"
)

var sc = bufio.NewScanner(os.Stdin)

func main()  {
	var n int
	fmt.Scan(&n)

	v := make([]int,n)
	for i := 0; i < n; i++ {
		fmt.Scan(&v[i])
	}

	odd := make(map[int]int)
	even := make(map[int]int)
	maxOdd, maxOddVal, maxEven, maxEvenVal := 0, 0, 0, 0
	priorMaxOdd, priorMaxEven := 0, 0
	for i := 0; i < n; i++ {
		thisVal := v[i]
		if i % 2 == 0 {
			odd[thisVal]++
			if odd[thisVal] >= maxOddVal {
				maxOddVal = odd[thisVal]
				if maxOdd != thisVal{
					priorMaxOdd = maxOdd
				}
				maxOdd = thisVal
			}
		} else {
			even[thisVal]++
			if even[thisVal] >= maxEvenVal {
				maxEvenVal = even[thisVal]
				if maxEven != thisVal{
					priorMaxEven = maxEven
				}
				maxEven = thisVal
			}
		}
	}
	if maxOdd == maxEven {
		if odd[priorMaxOdd] + maxEvenVal < even[priorMaxEven] + maxOddVal {
			fmt.Println(outVal(n, maxOddVal, even[priorMaxEven]))
		} else {
			fmt.Println(outVal(n, odd[priorMaxOdd], maxEvenVal))
		}
	}else {
		fmt.Println(outVal(n, maxOddVal, maxEvenVal))
	}
}

func outVal(n, odd, even int) int {
	return n - odd - even
}


Measured memory_bytes: 6656
#![allow(unused_macros)]
#![allow(dead_code)]
#![allow(unused_imports)]

use text_io::*;

fn main() {
    const I_INF: usize = 1 << 50;
    const U_INF: isize = 1 << 50;
    
    let n: usize = read!();
    let w: usize = read!();
    
    let mut vs = Vec::with_capacity(n);
    let mut ws = Vec::with_capacity(n);
    
    for _ in 0..n {
        let wi: usize = read!();
        let vi: usize = read!();
        ws.push(wi);
        vs.push(vi);
    }
    
    let mut dp = vec![vec![0; w + 10]; n + 10];
    for i in 0..n {
        for cap in (0..=w).rev() {
            if cap >= ws[i] {
                dp[i + 1][cap - ws[i]] = dp[i + 1][cap - ws[i]].max(dp[i][cap].clone() + vs[i]);
            }
            dp[i + 1][cap] = dp[i + 1][cap].max(dp[i][cap].clone());
        }
    }
    
    println!("{}", dp[n].iter().max().unwrap());
}

Measured memory_bytes: 87508
#include <bits/stdc++.h>
#define rep(a,n) for (ll a = 0; a < (n); ++a)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<vector<ll> > Graph;
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; }
const ll INF = 1e18;

int main(){
    ll n,m;
    cin >> n >> m;
    vector<ll>a(n);
    rep(i,n){
        cin>>a[i];
        a[i] %= m;
    }
    vector<ll>r(n+1,0);
    map<ll,ll>mp;
    mp[0]++;
    rep(i,n){
        r[i+1] = r[i]+a[i];
        r[i+1] %= m;
        mp[r[i+1]]++;
    }
    ll ans = 0;
    for(auto it = mp.begin();it!=mp.end();it++){
        ll now = it->second;
        ans += (now-1)*now/2;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 5760
#include <bits/stdc++.h>
//For ordered_set
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define MOD 1000000007
#define test int t; cin>>t; while(t--)
#define init(arr,val) memset(arr,val,sizeof(arr))
#define loop(i,a,b) for(int i=a;i<b;i++)
#define loopr(i,a,b) for(int i=a;i>=b;i--)
#define loops(i,a,b,step) for(int i=a;i<b;i+=step)
#define looprs(i,a,b,step) for(int i=a;i>=b;i-=step)
#define ull unsigned long long int
#define ll long long int
#define P pair
#define PLL pair<long long, long long>
#define PII pair<int, int>
#define PUU pair<unsigned long long int, unsigned long long int>
#define L list
#define V vector
#define D deque
#define ST set
#define MS multiset
#define M map
#define UM unordered_map
#define mp make_pair
#define pb push_back
#define pf push_front
#define MM multimap
#define F first
#define S second
#define IT iterator
#define RIT reverse_iterator
#define FAST ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define FILE_READ_IN freopen("input.txt","r",stdin);
#define FILE_READ_OUT freopen("output.txt","w",stdout);
#define all(a) a.begin(),a.end()
using namespace std;
// For ordered_set
using namespace __gnu_pbds;
template <typename T>
using ord_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll maxn = 1e5;
const ll inf = 1e9;
const double pi = acos(-1);

void solve()
{
    int s,w; cin >> s >> w;
    if (w>= s)
    {
        cout << "unsafe" << "\n";
    }
    else
    {
        cout << "safe" << "\n";
    }
    
    
}

int main()
{
   solve();
   return 0;
}

Measured memory_bytes: 3620
/*
                                                  __          __
      /\   |   |     /\   |  | |  |     /\   | / |  )   /\   |  )
     /__\  |   |    /__\  |--| |  |    /__\  |<  |-<   /__\  |-<
    /    \ |__ |__ /    \ |  | \__/   /    \ | \ |__) /    \ |  \

*/

#import<bits/stdc++.h>
typedef long long ll;
#define num 1e9
#define root 10000
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define forll(i,a,b,c) for(int i=a; i<=b; i+=c)
#define forll2(i,a,b,c) for(int i=a; i>=b; i-=c)
#define pb(n) push_back(n)
#define i(n) insert(n)

using namespace std;

int main()
{
    io;
    int n;
    ll x=0;
    cin>>n;
    int a[n];
    forll(i,0,n-1,1)
    {
        cin>>a[i];
    }
    forll(i,1,n-1,1)
    {
        if(a[i]<a[i-1])
        {
            x+=(a[i-1]-a[i]);
            a[i]=a[i-1];
        }
    }
    cout<<x<<"\n";
}


Measured memory_bytes: 4440
#include <bits/stdc++.h>
#define MODNum 1000000007
#define WHITE  0
#define GRAY   1
#define BLACK  2
#define INFTY  2147483647
#define REP(type, i, a, b) for( type i = a; i < b; i++ )
typedef long long ll;

using namespace std;

int main (void) {
    ll N, E, r;
    scanf("%lld %lld %lld", &N, &E, &r);
    int u,v,k;
    //ll c[N][N];    /* 辺の重みを記録した隣接行列 */
    ll d[N];       /* 最短コストの記録 */
    priority_queue<pair<ll,ll>> pq;
    //int p[N];       /* 最短経路木における頂点vの親 */
    int weight;
    vector< vector<pair<ll,ll>> > G(N);

    /* Initialization */
    for ( int i = 0; i < N; i++ ){
        d[i]     = INFTY;
        if ( r == i ){
            pq.push(make_pair(0,i));
            d[i] = 0;
        }
        else{
            pq.push(make_pair(-INFTY,i));
        }
        //p[i]  =  -1;
        //for ( int j = 0; j < N; j++ ) c[i][j] = INFTY;
    }
    /* グラフを読み込み */
    for ( int i = 0; i < E; i++ ){
            scanf("%d %d %d", &u, &v, &weight);
            //c[u][v] = weight;
            G[u].push_back( make_pair(weight, v) );
    }

    while ( !pq.empty() ){
        pair<ll,ll> edgepair  =  pq.top();
        pq.pop();
        u                       =  edgepair.second;
        if ( d[u] < -edgepair.first ) continue;
        //for ( v = 0; v < N; v++ ){
            for ( auto& e:G[u])
          //  if ( c[u][v] != INFTY ){
                if ( d[e.second]    > d[u] + e.first ){
                    d[e.second]     = d[u] + e.first;
                    //p[v]     = u;
                    pq.push(make_pair(-d[e.second],e.second));
                }
            //}
        //}
    }

    for ( int i = 0; i < N; i++ ){
        if ( d[i] != INFTY )
            printf("%d\n", d[i]);
        else printf("INF\n");
    }

    return 0;
}



Measured memory_bytes: 21360
#include <vector>
#include <iostream>
using namespace std;
int main() {
	int N;
	cin >> N;
	vector<int> T = { 0 }, X = { 0 }, Y = { 0 };
	for (int i = 0; i < N; i++) {
		int t, x, y;
		cin >> t >> x >> y;
		T.push_back(t);
		X.push_back(x);
		Y.push_back(y);
	}
	for (int i = 1; i <= N; i++) {
		int span = T[i] - T[i - 1];
		int step = abs(X[i] - X[i - 1]) + abs(Y[i] - Y[i - 1]);
		if ((step > span) || (span % 2 != step % 2)) {
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
}

Measured memory_bytes: 1644
#include<bits/stdc++.h>
using namespace std;
string a,yl="AKIHABARA";
int now,k;
int main()
{
    cin>>a;
    for(int s=0;s<a.size();s++)
    {
        if(a[s]==yl[now])//匹配成功
        {
            now++;
        }
        else//匹配不成功
        {
            if(s>0)
            if(a[s]==a[s-1])//连续两个一样
            {
                cout<<"NO"<<endl;
                exit(0);
            }
            if(yl[now]=='A')now++,s--;//是A，pass
            else//不是A，输出NO
            {
                cout<<"NO"<<endl;
                exit(0);
            }
        }
    }
    k=a.size();//最后，查错
    for(int s=0;s<a.size();s++)
    {
        if(a[s]=='A')k--;
    }
    if(k==5)
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
    int i,j,ch[1000000];

    for(i=0;i<1000000;i+=2){ch[i]=0;ch[i+1]=1;}

    ch[1]=0;
    ch[2]=1;

    for(i=3;i<1000;i+=2) if(ch[i]) for(j=i<<1;j<1000000;j+=i) ch[j]=0;

    for(i=3;i<1000000;i++) ch[i]+=ch[i-1];

    while(cin>>i) cout<<ch[i]<<endl;

    return 0;
}

Measured memory_bytes: 6864
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int RLEN=1<<18|1;
inline char nc() {
	static char ibuf[RLEN],*ib,*ob;
	(ib==ob) && (ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
	return (ib==ob) ? -1 : *ib++;
}
inline int rd() {
	char ch=nc(); int i=0,f=1;
	while(!isdigit(ch)) {if(ch=='-')f=-1; ch=nc();}
	while(isdigit(ch)) {i=(i<<1)+(i<<3)+ch-'0'; ch=nc();}
	return i*f;
}

const int N=1e5+50;
int n,rt,a[N]; LL f[N];
vector <int> edge[N];
inline void dfs(int x,int fa) {
	if(edge[x].size()==1) {f[x]=a[x]; return;}
	LL sum=0;
	for(int e=edge[x].size()-1;e>=0;e--) {
		int v=edge[x][e]; if(v==fa) continue;
		dfs(v,x); sum+=f[v];
		if(f[v]>a[x]) {puts("NO"); exit(0);}
	}
	if(sum<a[x] || sum-a[x]>a[x]) {puts("NO"); exit(0);}
	f[x]=a[x]-(sum-a[x]);
}

int main() {
	n=rd();
	for(int i=1;i<=n;i++) a[i]=rd();
	if(n==2) {puts((a[1]==a[2]) ? "YES" : "NO"); return 0;}
	for(int i=1;i<n;i++) {
		int x=rd(), y=rd();
		edge[x].push_back(y);
		edge[y].push_back(x);
	}
	while(edge[rt].size()<=1) ++rt;
	dfs(rt,0); puts(f[rt] ? "NO" : "YES");
}

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

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

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

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

inline void read() {}

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

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

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

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

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

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    var(int, N);
    vector<int> a(N);
    read(a);
    sort(all(a));

    int ans = 0;
    rep(i, 0, N) rep(j, i + 1, N) {
        const auto bgn = begin(a) + j + 1;
        ans += lower_bound(bgn, end(a), a[i] + a[j]) - bgn;
    }

    print(ans);

    return 0;
}


Measured memory_bytes: 256
//Twitter@KonoLv1 2020年春からエンジニア見習いデビュー！
 
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
 
int main(void){
    int i,j;            //  ループ文に使用
    int x,y,z;
    int count1,count2,count;   //  カウント用に使用
    int boxa[1024] = {};
    int boxb[1024] = {};
    char s[200001] = {};        //  文字列
    char s2[200001] = {};        //  文字列
    int a,b,c,h,w;
    int n,k;
    a = b = c = i = 0;
    int mode = 0;
    count = count1 = count2 = 0;
 
    //  入力処理
    
    scanf("%d %d",&n,&k);
    for (i = 0; i < n; i++){
        scanf("%d",&x);
        if (x >= k){
            count++;
        }
    }
 
    //  計算処理
    
 
 
    //  出力処理
 
    printf("%d",count);

 
}

Measured memory_bytes: 128
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)

H, W = map(int, input().split(" "))
S = [input() for _ in range(H)]

white = 0
black = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            white += 1
        else:
            black += 1
cnt = [[-1]*W for _ in range(H)]

def bfs():
    queue = deque([[0, 0]])
    cnt[0][0] = 0
    while queue:
        y, x = queue.popleft()
        for dy, dx in [[1,0], [-1,0], [0,1], [0,-1]]:
            if y+dy >= 0 and y+dy < H and x+dx >= 0 and x+dx < W:
                if cnt[y+dy][x+dx] == -1 and S[y+dy][x+dx] == ".":
                    cnt[y+dy][x+dx] = cnt[y][x] + 1
                    queue.append([y+dy,x+dx])

bfs()
if cnt[H-1][W-1] == -1:
    print("-1")
else:
    print(white-cnt[H-1][W-1]-1)

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

using namespace std;


int main()
{
  int n;
  cin >> n;
  vector<int> storage(n);
  for (int i = 0; i < n; ++i)
  {
    cin >> storage[i];
  }
  sort(storage.begin(), storage.end());
  double sum = storage[0] + storage[1];
  sum /= (double)2;
  for (int i = 2; i < n; ++i)
  {
    sum += storage[i];
    sum /= (double)2;
  }
  cout << sum << endl;

  return 0;
}

Measured memory_bytes: 256
N = int(input())
W = list(map(int, input().split()))

ttl = sum(W)
s = []
min = ttl

for i in range(len(W)):
    s.append(W[i])
    s2 = ttl - sum(s)
    if abs(sum(s) - s2) < min:
        min = abs(sum(s) - s2)
        
print(min)

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

using namespace std;

const int N=271199;

int main(){
	#ifndef ONLINE_JUDGE
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	#endif
	ios::sync_with_stdio(false);cin.tie(0);
	/*Input*/
	int n,k;
	cin >> n >> k;
	vector<int> h(n);
	for (int i=0;i<n;i++)
		cin >> h[i];
	/*Process*/
	vector<int> dp(n,0);
	dp[1]=abs(h[1]-h[0]);
	for (int i=2;i<n;i++){
		dp[i]=dp[i-1]+abs(h[i]-h[i-1]);
		for (int j=i-2;j>=max(0,i-k);j--)
			dp[i]=min(dp[j]+abs(h[i]-h[j]),dp[i]);
	}
	//Ideas:
	cout << dp[n-1] << '\n';
	/*Out*/
	return 0;
}

Measured memory_bytes: 1024
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner scanner = new Scanner(System.in);
		String S = scanner.nextLine();
		String T = scanner.nextLine();
		int count = 0;
		if(S.substring(0,1).equals(T.substring(0,1))){
			count++;
		}if(S.substring(1,2).equals(T.substring(1,2))){
			count++;
		}if(S.substring(2,3).equals(T.substring(2,3))){
			count++;
		}
		System.out.println(count);
		}
	}


Measured memory_bytes: 23252
n=int(input())
z_max,z_min=-10**10,10**10
w_max,w_min=-10**10,10**10
for i in range(n):
    a,b=map(int,input().split())
    z=a+b
    w=a-b
    z_max=max(z_max,z)
    z_min=min(z_min,z)
    w_max=max(w_max,w)
    w_min=min(w_min,w)
print(max(z_max-z_min,w_max-w_min))

Measured memory_bytes: 9120
#D
import math
N = int(input())
Nsyo = N
count = 0
div = 2
divcount = 0
divlist = []
while N > 1 and div <= math.sqrt(Nsyo)+1:
    if N%div == 0:
        while N%div == 0:
            N = N/div
            divcount = divcount+1
        divlist.append(divcount)
        divcount = 0
    else:
        pass
    div = div + 1
div = 1
divcount = 0
for i in divlist:
    while i >= div:
        i = i-div
        divcount = divcount + 1
        div = div + 1
        
    count = count +divcount
    divcount = 0
    div = 1
if N > math.sqrt(Nsyo):
    count = count + 1
print(count)

Measured memory_bytes: 9292
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <map>
#include <iomanip>
#include <math.h> 
#include <stack>
#include <queue>
#include <bitset>

using namespace std;

int main() {
	int i, j, k;
	int h, w, d, a[305][305];
	int q, l[100005] = { 0 }, r[100005] = { 0 };
	//int zure[90005] = { 0 };
	int x[90005] = { 0 }, y[900005] = { 0 };

	cin >> h >> w >> d;

	//int cnt = 0;
	for (i = 0; i < h; i++) {
		for (j = 0; j < w; j++) {
			cin >> a[i][j];
			x[a[i][j]] = j;
			y[a[i][j]] = i;
		}
	}

	cin >> q;

	for (i = 0; i < q; i++) {
		cin >> l[i] >> r[i];
	}

	map<int, int>m;
	int zu = 0;
	for (i = 1; i < d+1; i++) {
		zu = 0;
		for (j=i; j<=h*w; j+=d) {
			//if (j == h*w) continue;

			m.insert(pair<int, int>(j, zu));

			if (j == h*w) continue;

			zu = zu + abs(x[j+d]-x[j]) + abs(y[j+d]-y[j]) ;
			

		}

	}



	for (i = 0; i < q; i++) {
		cout << m[r[i]] - m[l[i]] << endl;

	}








	//getchar();
	//getchar();
	return 0;
}

Measured memory_bytes: 10368
def make(n):
    C = {0: 0}
    for i in range(n):
        b = int(input(), 2)
        for k, v in dict(C).items():
            if C.get(k^b, 0) < v+1:
                C[k^b] = v+1
    return C
def calc(P, Q):
    yield 0
    for k, v in P.items():
        if k in Q:
            yield v + Q[k]
def solve():
    while 1:
        n, m = map(int, input().split())
        if n+m == 0:
            break
        yield max(calc(make(n//2), make(n-n//2)))
print(*solve(), sep="\n")

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

using namespace std;

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

#define ff first
#define ss second

const int maxn = 1e5+10;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,m,x;
	ll ans=1e9+10;
	cin >> n >> m >> x;
	vector<int> c(n);
	vector<vector<int>> a(n,vector<int>(m));
	for(int i=0;i<n;++i){
		cin >> c[i];
		for(int j=0;j<m;++j){
			cin >> a[i][j];
		}
	}
	for(int i=0;i<(1<<n);++i){
		ll s=0;
		bool ok = true;
		vector<int> tmp(m);
		for(int j=0;j<n;++j){
			if((i&(1<<j))!=0){
				s+=c[j];
				for(int k=0;k<m;++k){
					tmp[k]+=a[j][k];
				}
			}
		}
		for(int j=0;j<m;++j){
			//cout << "s = " << s << " tmp[j] = " << tmp[j] << '\n';
			if(tmp[j]<x)
				ok = false;
		}
		if(ok)
			ans=min(ans,s);
	}
	cout << (ans!=1e9+10 ? ans : -1) << '\n';
	return 0;
}

Measured memory_bytes: 3664
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
typedef long long int ll;
int main(){
ll n,a,b;
cin >>n;
cin >>a>>b;
ll p[n],aa=0,ab=0,bb=0;
for(ll i=0;i<n;i++) {
  cin >>p[i];
  if(p[i]<=a) aa++;
  else if(p[i]<=b) ab++;
  else bb++;
}
cout << min(bb,min(aa,ab))<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
	int n, p[100], i, s;
	while (cin >> n && n)
	{
		for (i = 0; i < n; i++)
			cin >> p[i];
		sort(p, p+n);
		for (i = 1, s = 0; i < n-1; i++)
			s += p[i];
		cout << s / (n-2) << endl;
	}
}

Measured memory_bytes: 0
n=int(input())
s=list(map(int,input().split()))
f=True
for i in range(n-1,0,-1):
    if s[i]<s[i-1]:
        s[i-1]-=1
for i in range(n-1,0,-1):
    if s[i]<s[i-1]:
        f=False
if f:
    print("Yes")
else:
    print("No")


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

using namespace std;

int N;
int a[50];
vector<int> opex;
vector<int> opey;
int count;

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

    int maxa = a[0];
    int indma = 0;
    for(int i=1; i<N; i++) {
        if(abs(maxa) < abs(a[i])) {
            maxa = a[i];
            indma = i;
        }
    }
    if(maxa == 0) {
        puts("0"); return 0;
    }
    bool plus = maxa > 0;
    for(int i=0; i<N; ++i) {
        if(plus&&a[i]<0 || !plus&&a[i]>0) {
            a[i] += maxa;
            opex.push_back(indma+1);
            opey.push_back(i+1);
            count++;
        }
    }

    cout << count + N-1 << endl;
    for(int i=0; i<count; i++) {
        cout << opex[i] << " " << opey[i] << endl;
    }
    for(int i=1; i<N; i++) {
        int x = plus ? i : N-i+1;
        int y = plus ? i+1 : N-i;
        cout << x << " " << y << endl;
    }
    return 0;
}


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

const int N = 101010;
typedef long long ll;

inline char get(void) {
	static char buf[100000], *S = buf, *T = buf;
	if (S == T) {
		T = (S = buf) + fread(buf, 1, 100000, stdin);
		if (S == T) return EOF;
	}
	return *S++;
}
template<typename T>
inline void read(T &x) {
	static char c; x = 0;
	for (c = get(); c < '0' || c > '9'; c = get());
	for (; c >= '0' && c <= '9'; c = get()) x = x * 10 + c - '0';
}

long long n, L, T, bg, dis, delta, f1;
int x[N], w[N];
int f[N], ans[N];

int main(void) {
	read(n); read(L); read(T);
	for (int i = 1; i <= n; i++) {
		read(x[i]); read(w[i]);
		if (w[i] == 1) f[i] = (x[i] + T) % L;
		else f[i] = (x[i] - T % L + L) % L;
	}
	f1 = f[1]; T <<= 1;
	sort(f + 1, f + n + 1);
	for (int i = 2; i <= n; i++)
		if (w[i] ^ w[1]) {
            if (w[1] == 1) dis = T - x[i] + x[1] - 1;
			else dis = T - L + x[i] - x[1] - 1;
			delta += (dis < 0 ? 0 : (dis / L + 1));
		}
	if (w[1] == 2) delta = (n - delta % n) % n;
	bg = delta % n + 1;
	if (w[1] == 1) {
		for (int i = 1; i <= n; i++)
			if (f[i] == f1) {
				f1 = i; break;
			}
	} else {
		for (int i = n; i >= 1; i--)
			if (f[i] == f1) {
				f1 = i; break;
			}
	}
	for (int i = 1; i <= n; i++) {
		ans[bg] = f[f1];
		bg = bg % n + 1;
		f1 = f1 % n + 1;
	}
	for (int i = 1; i <= n; i++) printf("%d\n", ans[i]);
	return 0;
}

Measured memory_bytes: 2816
R, C = map(int, input().split())
maze =["#"*(C+2)]+["#"+input()+"#" for i in range(R)]+["#"*(C+2)]
visited = [[0]*(C+2) for j in range(R+2)]
INF=10**9+7
for i in range(1,R+1):
    for j in range(1,C+1):
        if i==1 and j==1:visited[1][1]=1
        elif maze[i][j]==".":
            visited[i][j]=(visited[i-1][j]+visited[i][j-1])%INF
            if i==R and j==C:print(visited[i][j])

Measured memory_bytes: 43612
from bisect import *
from collections import *
from itertools import *
import functools
import sys
import math
from decimal import *
from copy import *
from heapq import *
from fractions import *
getcontext().prec = 30
MAX = sys.maxsize
MAXN = 10**5+10
MOD = 10**9+7
spf = [i for i in range(MAXN)]
spf[0]=spf[1] = -1
def sieve():
    for i in range(2,MAXN,2):
        spf[i] = 2
    for i in range(3,int(MAXN**0.5)+1):
        if spf[i]==i:
            for j in range(i*i,MAXN,i):
                if spf[j]==j:
                    spf[j]=i
def fib(n,m):
    if n == 0:
        return [0, 1]
    else:
        a, b = fib(n // 2)
        c = ((a%m) * ((b%m) * 2 - (a%m)))%m
        d = ((a%m) * (a%m))%m + ((b)%m * (b)%m)%m
        if n % 2 == 0:
            return [c, d]
        else:
            return [d, c + d]

def charIN(x= ' '):
    return(sys.stdin.readline().strip().split(x))

def arrIN(x = ' '):
    return list(map(int,sys.stdin.readline().strip().split(x)))

def ncr(n,r):
    num=den=1
    for i in range(r):
        num = (num*(n-i))%MOD
        den = (den*(i+1))%MOD

    return (num*(pow(den,MOD-2,MOD)))%MOD

def flush():
    return sys.stdout.flush()

'''*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*'''
n,k = arrIN()
a = arrIN()
if k>=n:
    print(0)
else:
    a.sort()
    for i in range(k):
        a.pop()
    print(sum(a))



Measured memory_bytes: 32492
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;

int main(){
  int n,ans = 0;
  cin >> n;
  int p[n];
  REP(i,n) {
    cin >> p[i];
  }
  sort(p, p+n);
  for (int i = 0;i < n;i++) {
    if (i == n-1) {
      ans+= p[i]/2;
    } else {
    ans += p[i];
    }
  }
  cout << ans;
} 

Measured memory_bytes: 256
import sys
input = sys.stdin.readline  #文字列入力では注意！

A,B,M = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
ans = min(a)+min(b)

for i in range(M):
    x,y,c = map(int,input().split())
    ans = min(ans,a[x-1]+b[y-1]-c)
print(ans)


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

int main(){
  int H,W;
  cin >> H >> W;
  vector<vector<string>> S(H,vector<string>(W));
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cin >> S.at(i).at(j);
      if(S.at(i).at(j)=="snuke"){
        char A='A'+j;
        cout << A << i+1 << endl;
      }
    }
  }
}

Measured memory_bytes: 3592
#include<stdio.h>

#define BSIZE 16
int is;
char ib[BSIZE], ob[BSIZE], *ip, *op;
void mystart();
void myexit();
void put(char c);
char get();

short nextShort();
void printInt(int f);

int min(int a, int b){return a>b?b:a;}
int dif(short a, int b){return a<b?b-a:a-b;}

short N, j;
int l, i;
short A, B, C, L[8];
int a[4], b[4];
int ans, now;

int main(){
	mystart();
	N=nextShort();
	A=nextShort();
	B=nextShort();
	C=nextShort();
	for(i=0; i<N; i++){
		L[i]=nextShort();
	}
	ans = 2147483647;
	for(i=0, l=(1<<(N<<1)); i<l; i++){
		a[0]=a[1]=a[2]=a[3]=0;
		b[0]=b[1]=b[2]=b[3]=0;
		for(j=0; j<N; j++){
			a[(i>>(j<<1))&3] ++;
			b[(i>>(j<<1))&3] += L[j];
		}
		if(a[0]==0 || a[1]==0 || a[2]==0){continue;}
		now = (a[0]+a[1]+a[2]-3)*10 + dif(A, b[0])+dif(B, b[1])+dif(C, b[2]);
		ans = min(ans, now);
	}
	printInt(ans);
	put(10);
	myexit();
}

void mystart(){ip = ib + BSIZE; op = ob; is = 0;}
void myexit(){fwrite(ob, 1, op - ob, stdout);}
void put(char c){if(op==ob+BSIZE){fwrite(ob, 1, BSIZE, stdout); op = ob;} *op++ = c;}
char get(){if(ip==ib+BSIZE){is = fread(ib, 1, BSIZE, stdin); ip = ib;} return (ip==ib+is)?0:*ip++;}
short nextShort(){short f=0; char c=get(); while((c<'0')||('9'<c)){c=get();} while((c>='0')&&(c<='9')){f=f*10+(c-'0'); c=get();} return f;}
void printInt(int f){char c[16]; if(!f){put('0'); return;} char i=0; while(f){c[++i]=(f%10)^48; f/=10;} while(i){put(c[i--]);}}


Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>

#define rep(i,n) for(int i = 0; i < n; ++i)
#define reps(i,f,n) for(int i = f; i < n; ++i)
#define pb push_back
using namespace std;
using ll=long long;

template<typename T>
class ShortestPath{
  public:
    class Edge{
      public:
        T val;
        int to;
        Edge(T v, int t):val(v), to(t){}
    };

    int n;
    vector< vector<Edge> > g;
    vector<T> d;
    vector<T> p;
    vector<int> used;
    vector<vector<T> > tmp;
    T INF;
    using PTI=pair<T,int>;


    ShortestPath(int _n, const T inf):n(_n),g(n),d(n),p(n), INF(inf){
    }

    void dijkstra(int s){
      priority_queue<PTI, vector<PTI>, greater<PTI> > pq;
      used.resize(n, 0);
      rep(i,n){
        d[i] = INF;
        p[i] = -1;
      }
      d[s] = 0;
      pq.push(PTI(0, s));
      while(!pq.empty()){
        T val = pq.top().first;
        int current = pq.top().second;
        pq.pop();
        if(used[current])continue;
        used[current] = 1;
        rep(i, g[current].size()){
          Edge e = g[current][i];
          if( d[e.to] > d[current] + e.val){
            d[e.to] = d[current] + e.val;
            p[e.to] = current;
            pq.push(PTI(d[e.to], e.to));
          }
        }
      }
    }


    bool bellman_ford(int s){
      rep(i,n){
        d[i] = INF;
        p[i] = -1;
      }
      d[s] = 0;

      reps(i,1,n-1){
        rep(j, g.size()){
          if(d[j] == INF)continue;
          rep(k, g[j].size()){
            int u = j;
            int v = g[j][k].to;
            T c = g[j][k].val;
            if( d[v] > d[u] + c){
              d[v] = d[u] + c;
              p[v] = u;
            }
          }
        }
      }
      rep(i, g.size()){
        if(d[i] == INF)continue;
        rep(j, g[i].size()){
          int u = i;
          int v = g[i][j].to;
          T c = g[i][j].val;
          if( d[v] > d[u] + c){
            return false;
          }
        }
      }
      return true;
    }

    bool warshall_floyd(){
      tmp.resize(n, vector<T>(n,INF));

      rep(i,n)tmp[i][i] = 0;
      rep(i,n)rep(j, g[i].size()){
        tmp[i][g[i][j].to] = g[i][j].val;
      }
      rep(i,n)tmp[i][i] = 0;

      rep(k,n)rep(i,n)rep(j,n){
        if(tmp[i][k] == INF || tmp[k][j] == INF)continue;
        tmp[i][j] = min(tmp[i][j], tmp[i][k] + tmp[k][j]);
      }
      rep(k,n)rep(i,n)rep(j,n){
        if(tmp[i][k] == INF || tmp[k][j] == INF)continue;
        if(tmp[i][j] > tmp[i][k] + tmp[k][j]){
          return false;
        }
      }
      return true;
    }
};

int main(void){
  int v, e, r;
  int s,t,d;
  cin >> v >> e;
  const ll inf = 1000000000000LL;
  ShortestPath<ll> sp(v, inf);
  rep(i,e){
    cin >> s >> t >> d;
    sp.g[s].pb(ShortestPath<ll>::Edge(d, t));
  }
//   sp.dijkstra(r);
  bool res = sp.warshall_floyd();
  if(res){
    rep(i,v){
      rep(j, v){
        if(sp.tmp[i][j] == inf){
          cout << "INF";
        }else{
          cout << sp.tmp[i][j];
        }
        if(j != v-1)cout << " ";
      }
      cout << endl;
    }
  }else{
    cout << "NEGATIVE CYCLE" << endl;
  }

  return 0;
}

Measured memory_bytes: 3320
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
inline ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
inline ll lcm(ll a, ll b) { return a / gcd(a, b)*b; }
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T>& V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> >& Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T>& mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }
template<typename T>vector<T> make_v(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>auto make_v(size_t a,Ts... ts){return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t,const V &v){t=v;}
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t,const V &v){for(auto &e:t) fill_v(e,v);}
/*
 <url:>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */

template<class Type>
Type solve(Type res = Type()){
    ll a; cin >> a;
    string s; cin >> s;
    if(a >= 3200) return s;
    return res = "red";
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    // solve(0);
    cout << fixed << setprecision(15) << solve<string>() << endl;
    return 0;
}


Measured memory_bytes: 256
//copied
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define MAXN 300005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
	if(c == '-') f = -1;
	c = getchar();
    }
    while(c >= '0' && c <= '9') {
	res = res * 10 +c - '0';
	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
	out(x / 10);
    }
    putchar('0' + x % 10);
}
struct cmp {
    bool operator () (const int &a,const int &b) const {
	return a > b;
    }
};
int N,a[MAXN];
int64 f[MAXN],b[MAXN];
multiset<int> s2;
multiset<int,cmp> s1;
void Solve() {
    read(N);
    for(int i = 1 ; i <= 3 * N ; ++i) read(a[i]);
    int64 sum = 0;
    for(int i = 1 ; i <= 3 * N ; ++i) {
	s1.insert(a[i]);sum += a[i];
	if(s1.size() > N) {
	    auto t = *(--s1.end());
	    s1.erase(--s1.end());
	    sum -= t;
	}
	f[i] = sum;
    }
    sum = 0;
    for(int i = 3 * N ; i >= 1 ; --i) {
	s2.insert(a[i]);sum += a[i];
	if(s2.size() > N) {
	    auto t = *(--s2.end());
	    s2.erase(--s2.end());
	    sum -= t;
	}
	b[i] = sum;
    }
    int64 ans = f[N] - b[N + 1];
    for(int i = N + 1 ; i <= 2 * N ; ++i) {
	ans = max(ans,f[i] - b[i + 1]);
    }
    out(ans);enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
}


Measured memory_bytes: 18852
#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>
#include<limits.h>
#include<string>
#include<math.h>
#include<map>
#include<deque>
#include<unordered_map>
using namespace std;




long long int getMin(long long int a, long long int b){
    if(a<b)
        return a;
    return b;
}

int main(){
    int n;
    int k;
    cin>>n;
    cin>>k;
    int h[n];
    for(int i=0;i<n;i++){
        cin>>h[i];
    }
    long long int ans[n+1];
    ans[0]=0;
    ans[1]=0;
    ans[2]=abs(h[0]-h[1]);
    for(int i=3;i<=n;i++){
        ans[i] = INT_MAX;
        for(int j=1;j<=k;j++){
            if(i-j>=1){
                ans[i] = getMin(ans[i],ans[i-j]+abs(h[i-j-1]-h[i-1]));
            }
            
        }
    }
    cout<<ans[n];
}






















Measured memory_bytes: 1408