akhauriyash/Code-Regression huggingface dataset:
# D - Wizard in Maze
import sys
from collections import deque
from typing import List, Tuple


class WarpableMaze:
    __slots__ = ["height", "width", "road", "wall", "grid"]

    def __init__(
        self,
        height: int,
        width: int,
        grid: List[str],
        road: str = ".",
        wall: str = "#",
    ) -> None:
        # Values of start and goal must be 0-origin.
        self.height = height + 4
        self.width = width + 4
        self.road = road
        self.wall = wall
        self.grid = self._flatten_grid(grid)

    def _flatten_dxy(self, x: int, y: int) -> int:
        return self.width * x + y

    def _flatten_coordinate(self, h: int, w: int) -> int:
        return self._flatten_dxy(h + 2, w + 2)

    def _flatten_grid(self, grid: List[str]) -> str:
        flat_grid = self.wall * self.width * 2
        for row in grid:
            flat_grid += self.wall * 2 + row + self.wall * 2
        flat_grid += self.wall * self.width * 2
        return flat_grid

    def bfs(self, start_2d: Tuple[int, int], goal_2d: Tuple[int, int]) -> int:
        start = self._flatten_coordinate(*start_2d)
        goal = self._flatten_coordinate(*goal_2d)
        
        w = self.width
        move_to_warp = {
            -w: (-2 * w - 2, -2 * w - 1, -2 * w, -2 * w + 1, -w - 1),
            w: (w + 1, 2 * w - 1, 2 * w, 2 * w + 1, 2 * w + 2),
            -1: (-w - 2, -2, w - 2, w - 1, 2 * w - 2),
            1: (-w + 1, -2 * w + 2, -w + 2, 2, w + 2),
        }

        unsearched = 1 << 30
        dist = [unsearched] * (self.height * self.width)
        dist[start] = 0
        queue = deque([start])
        while queue:
            x = queue.popleft()
            cur_dist = dist[x]
            if x == goal:
                break

            for move, warp in move_to_warp.items():
                nx = x + move
                if self.grid[nx] == self.road:
                    if dist[nx] > cur_dist:
                        dist[nx] = cur_dist
                        queue.appendleft(nx)
                    continue

                for dx in warp:
                    nx = x + dx
                    if self.grid[nx] == self.wall:
                        continue
                    if dist[nx] > cur_dist + 1:
                        dist[nx] = cur_dist + 1
                        queue.append(nx)

        return dist[goal] if dist[goal] != unsearched else -1

    def debug(self):
        print("<DEBUG>", file=sys.stderr)
        for row in zip(*[iter(self.grid)] * self.width):
            print(*row, file=sys.stderr)


def main():
    H, W, CH, CW, DH, DW, *S = open(0).read().split()
    maze = WarpableMaze(int(H), int(W), S)
    start, goal = (int(CH) - 1, int(CW) - 1), (int(DH) - 1, int(DW) - 1)
    print(maze.bfs(start, goal))
    # maze.debug()


if __name__ == "__main__":
    main()


Measured memory_bytes: 220068
def print_line(W, which_H):
    if which_H % 2 == 0:
        if W % 2 == 0:
            print(int(W/2) * "#.")
        else:
            print(int(W/2) * "#.", end="")
            print("#")
    else:
        if W % 2 == 0:
            print(int(W/2) * ".#")
        else:
            print(int(W/2) * ".#", end="")
            print(".")

while True:
    H, W = list(map(int, input().split()))
    if (H == 0) & (W == 0):
        break
    for h in range(H):
        print_line(W, h)
    print("")

Measured memory_bytes: 7740
from fractions import gcd
def lcm(x,y):return (x*y)//gcd(x,y)
n,m=map(int,input().split())
s,t=input(),input()
lcm=lcm(n,m)
if s[::int(lcm/m)]!=t[::int(lcm/n)]:print(-1);exit()
print(lcm)

Measured memory_bytes: 5344
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N,K;
  string S;
  cin>>N>>K>>S;
  if(S[K-1]=='A'){
    S[K-1]='a';
  }else if(S[K-1]=='B'){
    S[K-1]='b';
  }else{
    S[K-1]='c';
  }
  cout<<S<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define int long long

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

    int a, b;
    cin >> a >> b;
    cout << a*b << endl;
}


Measured memory_bytes: 3640
object Main {

  def main(args: Array[String]): Unit = {
    import scala.io.StdIn._
    
    val Array(n, m) = readLine().split(" ").map(_.toInt)
    val A: Array[Long] = readLine().split(" ").map(_.toLong).sorted
    val BC: Array[(Int, Long)] = (0 until m). map { _ =>
      val Array(_b, _c) = readLine().split(" ")
      (_b.toInt, _c.toLong)
    }. toArray. sortBy(_._2)(Ordering.Long.reverse)

    var ai = 0 // Aを見ている箇所
    var bci = 0 // BCを見ている箇所
    while (bci < m && ai < n && BC(bci)._2 > A(ai)) {
      val bc = BC(bci)._2 // 今回置き換える数
      var ic = 0
      while (ai < n && bc > A(ai) && ic < BC(bci)._1) {
        A(ai) = bc
        ic += 1
        ai += 1
      }
      bci += 1
    }
    println(A.sum)
  }

}

Measured memory_bytes: 82452
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,int> pi;
typedef tuple<int,int,int> piii;
const int INF=10000000;
#define pb(a) push_back(a)
#define m0(x) memset(x,0,sizeof(x))
#define print(x) cout<<x<<endl;
#define pe(x) cout<<x<<" ";
#define lb(v,n) lower_bound(v.begin(), v.end(), n);
#define ub(v,n) upper_bound(v.begin(), v.end(), n);
#define all(x) (x).begin(), (x).end()


int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  int n,m;
  cin >> n >> m;
  vector<vector<pii>> adj(1000000);
  vector<bool> visited(1000000,false);
  map<pii,int> ptr;
  int curr=n+1;
  while(m--){
    int v1,v2,c;
    cin >> v1 >> v2 >> c;

    if (ptr.find({v1,c})==ptr.end()){
      ptr[{v1,c}]=curr;
      adj[v1].push_back({curr,1});
      adj[curr].push_back({v1,0});
      curr++;
    }
    if (ptr.find({v2,c})==ptr.end()){
      ptr[{v2,c}]=curr;
      adj[v2].push_back({curr,1});
      adj[curr].push_back({v2,0});
      curr++;
    }

    int ptr1=ptr[{v1,c}];
    int ptr2=ptr[{v2,c}];

    // cout<<ptr1<<" "<<v1<<" "<<c<<endl;
    // cout<<ptr2<<" "<<v2<<" "<<c<<endl;

    adj[ptr1].push_back({ptr2,0});
    adj[ptr2].push_back({ptr1,0});


  }

  // for (int i=1; i<2*(n+m+100); i++){
  //   cerr<<"node = "<<i<<" | ";
  //   for (int j=0; j<adj[i].size(); j++){
  //     cerr<<adj[i][j].first<<" "<<adj[i][j].second<<"    ";
  //   }
  //   cerr<<endl;
  // }


  priority_queue <pii,vector<pii>,greater<pii>> pq;
  //set<pii> check;
  vector<int> distance(1000000,-1);
  distance[1]=0;
  pii temp={0,1};
  pq.push(temp);
  //visited.insert(temp);

  while(!pq.empty()){
    int curr_node=pq.top().second;
    int curr_cost=pq.top().first;
    pq.pop();

    if (!visited[curr_node]){
      visited[curr_node]=true;
      for (pii t: adj[curr_node]){
      int next_node=t.first;
      int cost=t.second;
      if (distance[next_node]>curr_cost+cost or distance[next_node]==-1){
        distance[next_node]=curr_cost+cost;
        pii temp={curr_cost+cost,next_node};
        pq.push(temp);
      }
    }
    }


  }


  cout<<distance[n]<<endl;







} 


Measured memory_bytes: 72952
import functools
import operator

n, a, b = map(int, input().split())

def nCr(n, r):
    r = min(r, n-r)
    if r == 0:
        return 1
    num = functools.reduce(lambda x, y: x*y%mod, range(n, n-r, -1))
    den = functools.reduce(lambda x, y: x*y%mod, map(lambda x: pow(x, mod-2, mod), range(1, r+1)))
    return num * den % mod

mod = 10**9 + 7
print((pow(2, n, mod) - nCr(n, a) - nCr(n, b) - 1) % mod)


Measured memory_bytes: 9540
#include<bits/stdc++.h>
#define ll long long
#define rint register int
using namespace std;
const int N=1e5+50;
int n,a[N<<1],Q,f[35][N],L;
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
  scanf("%d",&n);
  for(int i=1;i<=n;i++) scanf("%d",&a[i]); 
  scanf("%d",&L);
  for(int i=1;i<=n;i++)
    {
        int x=upper_bound(a+1,a+n+1,a[i]+L)-a-1;
        f[0][i]=x;
    }
  for(int j=1;j<=30;j++)
    for(int i=1;i<=n;i++)
      f[j][i]=f[j-1][f[j-1][i]];
  scanf("%d",&Q);
  while(Q--)
  {
  	int l,r,ans=0;
  	scanf("%d%d",&l,&r);
  	if(l>r) swap(l,r); 
  	for(int i=30;i>=0;i--)
  	{  
	  if(f[i][l]<r) l=f[i][l],ans+=(1<<i);	
  	}
  	printf("%d\n",ans+1);
  }
  return 0;
}


Measured memory_bytes: 15104
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>


using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD (ll)1000000007
#define P pair<ll, ll>

ll n;

int main() {
	cin >> n;
	cout << n * (n - 1) / 2 << endl;
}

	

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

int main () {
  string S;
  cin >> S;
  for (int i = 0; i < S.size(); i++) {

    if ((i + 1) % 2 == 0) { // Even
      if(S[i]== 'R') {
        cout << "No" << endl;
        return 0;
      }
    } else { // odd
      if(S[i] == 'L') {
        cout << "No" << endl;
        return 0;
      }
    }
  }
  cout << "Yes" << endl;
}

Measured memory_bytes: 256
using System;
class Program{
	static void Main(){
		int n=int.Parse(Console.ReadLine()),q=-1;
		int[] a=Array.ConvertAll(Console.ReadLine().Split(),int.Parse);
		int[] h=new int[21];
		for(int j=0;j<21;j++){h[j]=-1;}
		long ans=0;
		for(int i=0;i<n;i++){
			for(int j=0;j<21;j++){
				if((a[i]&(1<<j))!=0){
					q=Math.Max(q,h[j]);
					h[j]=i;
				}
			}
			ans+=i-q;
		}
		Console.WriteLine(ans);
	}
}

Measured memory_bytes: 32348
#include<iostream>
#include<vector>
#include<algorithm>
#include<complex>
using namespace std;
typedef long long int llint;
int main() {
	int a, b, c;
	cin >> a >> b >> c;
	if (b < c) {
		swap(b, c);
	}
	if (a < b) {
		swap(a, b);
	}
	if (a == 7 && b == 5 && c == 5) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;
use std::collections::HashSet;

fn main(){
    let s = read::<String>();
    let k = read::<usize>();
    let slen = s.len();
    let mut a = HashSet::new();
    for i in 0..slen as usize{
        for j in 0..k{
            if i+j>=slen{break;}
            //println!("{}",&s[i..i+j+1]);
            a.insert(&s[i..i+j+1]);
        }
    }
    //println!("{:?}",a);
    let mut b = vec![];
    for str in a{
        b.push(str);
    }
    b.sort();
    println!("{}",b[k-1]);
}
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin.bytes().map(|c| c.expect("Error") as char) 
        .skip_while(|c| c.is_whitespace()).take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("Error")
}

Measured memory_bytes: 6396
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,n,s) for(int i = s; i < (n); ++i)
#define rsrep(i,n,s) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<x<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define out_ary(...) { for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef vector<int> vint;
typedef vector<float> vfloat;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vstr> vvstr;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;

int main() {
    int n;
    cin >> n;
    vint a(n);
    rep(i, n) cin >> a[i];
    ll ans = LINF;
    ll ans_t, sign, total;

    rep(j, 2) {
        ans_t = 0;
        total = 0LL;
        if (j == 0) sign = true;
        else sign = false;
        rep(i, n) {
            total += a[i];
            if (sign) {
                if (total >= 0) {
                    ans_t += total + 1;
                    total = -1;
                }
            } else {
                if (total <= 0) {
                    ans_t += -1*total + 1;
                    total = 1;
                }
            }
            //cout << "i: " << i << " total: " << total << " ans_t: " << ans_t << endl;
            sign = 1 - sign;
        }
        ans = min(ans, ans_t);
    }

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

Measured memory_bytes: 768
/* ex5_4
   tamayama */

#include<stdio.h>
#define SIZE 11

int main(void){
    char str[SIZE];
    char *p;
    int len[SIZE];
    int *q;
    int count=0;
    int i;
    int max_len = 0;

    scanf("%s",str);
    p = str;
    q = len;

    for(i=0;i<SIZE;i++){    //int型配列の初期化
        len[i] = 0;
    }

    while(*p){    //連続するA,T,G,Cの数を数える
        if(*p == 'A'||*p == 'T'||*p == 'G'||*p == 'C'){
            while(*p == 'A'||*p == 'T'||*p == 'G'||*p == 'C'){
                count++;
                p++;
                q++;
            }
            *q = count;    //int型配列に何個連続したかを書き込む
            count = 0;
        }else{    //A,T,G,C以外は次の文字にポインタを移動
            p++;
            q++;
        }
    }

    for(i=0;i<SIZE;i++){    //int型配列のうち最大のものを求める
        if(max_len < len[i]){
            max_len = len[i];
        }
    }
    printf("%d",max_len);
    return 0;
}

Measured memory_bytes: 1732
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <bitset>
#include <queue>
#include <iostream>

using namespace std;

#define MAXN 510
#define INF 0x3f3f3f3f
typedef long long LL;

int main()
{
    int n, a, cnt = 0, vis[10] = {};
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i){
        scanf("%d", &a);
        if(a < 400) vis[0] = 1;
        else if(a < 800) vis[1] = 1;
        else if(a < 1200) vis[2] = 1;
        else if(a < 1600) vis[3] = 1;
        else if(a < 2000) vis[4] = 1;
        else if(a < 2400) vis[5] = 1;
        else if(a < 2800) vis[6] = 1;
        else if(a < 3200) vis[7] = 1;
        else ++cnt;
    }
    a = 0;
    for(int i = 0; i < 8; ++i)
        a += vis[i];
    printf("%d %d\n", a ? a : 1, a + cnt);
    return 0;
}


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

int main(){
  string s;
  int k;
  cin >> s;
  cin >> k;

  set<string> str;
  int size = s.size();
  for(int i=0;i<size;i++){
    for(int j=1; j <= k;j++){
      str.insert(s.substr(i, j));
    }
  }

  auto itr = str.begin();
  for(int i = 1; i <= k; i++){
    if(i==k)
      cout << *itr << endl;
    itr++;
  }
  return 0;
}


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

					#define F first
					#define S second
					#define N 222222
					#define M 1000000007
					#define pb push_back
					#define cend(s) return cout << s, 0
					using namespace std;
					typedef long long ll;
					typedef vector<int> vi;

					int main()
					{
						ll n, k, t;
						cin >> n >> k >> t;
						if(n % k)
							cout << (n/k + 1)*t;
						else cout << (n/k)*t;	 
					}

Measured memory_bytes: 3584
#include<iostream>
using namespace std;
int main(){
	int n,z,w;
	cin >> n >> z >> w;
	int a[2000];
	int maxindex=0;
	for(int i=0;i<n;i++) cin >> a[i];
	if(n==1) cout << abs(a[n-1]-w) << endl;
	else cout << max(abs(a[n-2]-a[n-1]),abs(a[n-1]-w)) << endl;
	return 0;
}


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

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define MOD 1000000007
#define INF (1LL<<25)     //33554432
#define PI 3.14159265359
#define EPS 1e-12
//#define int ll

signed main(void)
{
  ll n, m;
  cin >> n >> m;

  ll ans = 0;
  if(n*2 <= m) {
    ans += n;
    m -= 2*n;
    n = 0;
    ans += m/4;
  } else {
    ans += m/2;
  }

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


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int f(int a)
{
    int t=0;
    do{
        t+=a%10;
    }while (a/=10);
    return t;
}
int main() {

    int n,a,b,ans=0;
    cin >>n>>a>>b;
    for (int i=0;i<=n;i++)
        if (f(i)>=a && f(i)<=b)
            ans+=i;
    cout <<ans;
    
    return 0;
}



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

int main(){
  string s;
  cin >>s;
  sort(s.begin(),s.end());
  bool can = true;
  rep(i,s.size()-1){
    if(s[i]==s[i+1]) can = false;
  }
  if(can) cout << "yes" << endl;
  else cout << "no" << endl;  
  return 0;
}

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

using namespace std;

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

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

const ll MOD=1e9+7;
const ll INF=1e18;
const double pi=acos(-1);
const double eps=1e-10;

int dx[]={1, 0, -1, 0};
int dy[]={0, -1, 0, 1};

int main(){
    int a, b, c; cin>>a>>b>>c;
    cout << b + min(a + b + 1, c) << endl;
}

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

using bellman_cost = int;

template<class V, class E>
struct Graph
{
	int sz;
	vector<V> v;
	vector<vector<E>> e;
	Graph(int n) : sz(n), v(n), e(n) {}
	template<class... Args>
	inline void assign_vertex(int pos, Args... args) {
		v[pos] = V(args...);
	}
	// from, to, cost
	template<class... Args>
	inline void add_edge(int pos, Args... args) {
		e[pos].emplace_back(args...);
	}
	inline int size() {
		return sz;
	}
};

template<class T>
struct Vertex
{
	T cost;
	bool valid = false; // 到達不能または無限にコストが減るときfalse
	Vertex(T v1) : cost(v1) {}
	Vertex() {}
};
using vertex = Vertex<bellman_cost>;

template<class T>
struct Edge
{
	int to;
	T cost;
	Edge(int t, T c) : to(t), cost(c) {}
	Edge() {}
};
using edge = Edge<bellman_cost>;
using graph = Graph<vertex, edge>;

template<class T, class V, class E>
void Bellmanford(Graph<V, E>& G, int s, T INF_COST)
{
	auto &v = G.v;
	auto &e = G.e;
	for (auto& vv : v) vv.cost = INF_COST, vv.valid = false;
	v[s].cost = 0, v[s].valid = true;
	for (int i = 0; i + 1 < (int) v.size(); i++) {
		for (int j = 0; j < (int) v.size(); j++) {
			for (auto& x: e[j]) {
				if (v[j].cost == INF_COST) continue;
				v[x.to].cost = min(v[x.to].cost, v[j].cost + x.cost);
				v[x.to].valid = true;
			}
		}
	}
	auto valid_check = [&](auto f, int pos) {
		if (!v[pos].valid) return;
		v[pos].valid = false;
		for (auto& y: e[pos]) {
			f(f, y.to);
		}
	};
	for (int i = 0; i < (int) v.size(); i++) {
		for (auto& x: e[i]) {
			if (v[i].cost == INF_COST) continue;
			if (v[x.to].cost > v[i].cost + x.cost) {
				valid_check(valid_check, x.to);
			}
		}
	}
}


void solve(long long N, long long M, long long P, std::vector<long long> A, std::vector<long long> B, std::vector<long long> C) {
	graph g(N);
	for (int i = 0; i < M; i++) {
		g.add_edge(A[i]-1, B[i]-1, -(C[i]-P));
	}
	Bellmanford(g, 0, INT_MAX);
	if (!g.v[N-1].valid) cout << -1 << endl;
	else cout << max(-g.v[N-1].cost, 0) << endl;
}

signed main() {
	long long N;
	scanf("%lld",&N);
	long long M;
	scanf("%lld",&M);
	long long P;
	scanf("%lld",&P);
	std::vector<long long> A(M);
	std::vector<long long> B(M);
	std::vector<long long> C(M);
	for(int i = 0 ; i < M ; i++){
		scanf("%lld",&A[i]);
		scanf("%lld",&B[i]);
		scanf("%lld",&C[i]);
	}
	solve(N, M, P, std::move(A), std::move(B), std::move(C));
	return 0;
}


Measured memory_bytes: 512
K  = int(input())
n = 0
n1 = 0
n2 = 0
n3 = 0
n4 = 0
n5 = 0


#Kが500以下の場合、斜め作戦にする
if K <= 499:
   n = K
   mat = [[0 for n1 in range(K)] for n2 in range(K)]
   for n1 in range(K):
      for n2 in range(K-n1):
         mat[n1][n1+n2] = n2+1
   for n1 in range(K):
      for n2 in range(n1):
         mat[n1][n2] = K+n2-n1+1

#Kが500以上の場合、斜めに1マスずつしのびこませる   
else:
   n = 500
   mat = [[0 for n1 in range(500)] for n2 in range(500)]
   for n1 in range(500):
      for n2 in range(500-n1):
         mat[n1][n1+n2] = n2+1
   for n1 in range(500):
      for n2 in range(n1):
         mat[n1][n2] = 500+n2-n1+1

   #Kが500以上の場合のギザギザ部分
   for n2 in range(K-500):
      for n1 in range(250):
          kari = n1*2+n2
          if kari >= 500:
             kari = kari-500
          mat[n1*2][kari] = n2+501


#行列の出力かんがえとく 
print(n)

if K <= 500:
   out = ""
   for n1 in range(K):
      out = ""   
      for n2 in range(K):
         out = out + " " + str(mat[n1][n2])
      print(out)
   
#Kが500以上の場合、斜めに1マスずつしのびこませる   
else:
   out = ""
   for n1 in range(500):
       out = ""   
       for n2 in range(500):
          out = out + " " + str(mat[n1][n2])
       print(out)





Measured memory_bytes: 11936
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repp(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define rrep(i, n, m) for (int i = n; i >= m; i--)
#define p(s) cout << s << endl;
typedef long long LL;
template <class T>
bool contain(const std::string &s, const T &v)
{
    return s.find(v) != std::string::npos;
}

int main()
{
   string s1,s2,s3; cin>>s1>>s2>>s3;
   cout<<s1[0]<<s2[1]<<s3[2]<<endl;

}


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





main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;
    cin >> n;
    int a[n], b[n], sum = 0, cur = 0;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        sum += a[i];
    }
    for(int i = 0; i < n; i++){
        cin >> b[i];
    }
    int ans = 0;
    multiset < int > q;
    for(int i = 0; i < n; i++){
        if(a[i] < b[i]){
            a[i] = b[i];
            ans += 1;
        }
        else if(a[i] > b[i]){
            q.insert(a[i] - b[i]);
        }
        sum -= a[i];
        while(sum < 0 && !q.empty()){
            sum += *q.rbegin();
            ans += 1;
            q.erase(--q.end());
        }
        if(sum < 0){
            return cout << "-1", 0;
        }
    }
    cout << ans;
}


Measured memory_bytes: 3840
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <random>
#include <chrono>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
#define INF 1000000000
#define mod 1000000007


struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
    
    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }
    
    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }
    
    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }
    
    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};



int gcd(int a, int b){
    while(b){
        int t = a;
        a = b;
        b = t%b;
    }
    return a;
}

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



int main() {
    int N; cin >> N;
    vector<int> P(N);
    int mx = 0;
    int sum = 0;
    for(int i=0; i<N; i++){
        cin >> P[i];
        mx = max(mx, P[i]);
        sum += P[i];
    }
    
    cout << sum -  mx/2 << endl;
    
    
    return 0;
}


Measured memory_bytes: 256
/* SmartCoder Apr 7, 2019 */
#include <bits/stdc++.h>
using namespace std;

#define sz(a) int((a).size())
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end();i++)
#define present(c,x)  ( (c).find(x) !=(c).end())
#define cpresent(c,x) (find(all(c),x)!= (c).end() )
#define minei(x)  min_element(x.begin(),x.end())-(x).begin()
#define maxei(x)  max_element(x.begin(),x.end())-(x).begin()

#define uns(v)     sort((v).begin(),(v).end()),v.erase(unique(v.begin(),v.end()),v.end())
#define acusum(x)  accumulate(x.begin(),x.end(),0)
#define acumul(x)  accumulate(x.begin(),x.end(),1, multiplies<int>());
#define bits(x)     __builtin_popcount( x )
#define oo INT_MAX
#define inf 1000000000

const double pi = acos(-1.0);
const double eps = 1e-11;
#define MAXN 3003
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
void fastIO() {
	std::ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
double dp[MAXN];
int main() {
	fastIO();
	int n;
	double p_h;
	cin >> n;
	dp[0] = 1;
	for (int i = 0; i < n; i++) {
		cin >> p_h;
		for (int j = n + 1; j >= 0; j--) {
			dp[j] = (j == 0 ? 0 : dp[j - 1] * p_h) + dp[j] * (1 - p_h);
		}
	}
	cout<<fixed;
	cout<<setprecision(10);
	double res = 0;
	for (int i = n / 2 + 1; i <= n; i++)
		res += dp[i];
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <sstream>
#include <queue> 
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm> 
#include <numeric>  
#include <functional>
#include <cassert>
#include <bitset>
#include <cctype>  
#include <iomanip> 
#include <limits>  
#include <regex>
// std::numeric_limits<int>::max(), min()
// std::setprecision(X)
// std::islower(), std::isupper(), std::tolower, std::toupper
// std::accumulate(m.begin(), m.end(), 0LL);
// std::sort(begin(),end()) // 0, 1, 2, 3 ,4 (default, less);
// std::priority_queue<int, vector<int>, less<int>> que; // 4, 3, 2, 1 (defualt, less) : 
// if ( std::regex_match(S, std::regex("(dream|dreamer|erase|eraser)*")) ) std::cout << "YES" << std::endl;
 
#define rep(i, n) for(int i = 0; i < (int)(n);    i++)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

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

ll gcd ( ll a, ll b ) { if ( b == 0 ) return a; else return gcd ( b, a%b ); }
ll lcm ( ll a, ll b ) { return a * b / gcd(a, b); }


int main (void) {
  std::cin.tie(0);  std::ios::sync_with_stdio(false);
  int A, B; std::cin >> A >> B;
  std::cout << std::max(0, A-B-B) << std::endl;
  return 0;
}


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

int findSumOfDigits(int n){
  int sum = 0;
  while(n > 0){
    sum += n % 10;
    n /= 10;
  }
  return sum;
}

int main()
{
  int N, A, B;cin >> N >> A >> B;
  int total = 0;
  for(int i = 1; i <= N; ++i){
    int sum = findSumOfDigits(i);
    if (sum >= A && sum <= B){
      total += i;
    }
  }
  cout << total << endl;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAX 1400

int dp[MAX][MAX], G[MAX][MAX];

int getLargestSquare(int H, int W) {
	int maxWidth = 0;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			dp[i][j] = (G[i][j] + 1) % 2;
			maxWidth |= dp[i][j];
		}
	}

	for (int i = 1; i < H; i++) {
		for (int j = 1; j < W; j++) {
			if (G[i][j]) {
				dp[i][j] = 0;
			}
			else {
				dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
				maxWidth = max(maxWidth, dp[i][j]);
			}
		}
	}

	return maxWidth*maxWidth;
}

int main(void) {
	int H, W;
	scanf("%d %d", &H, &W);

	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++)scanf("%d", &G[i][j]);
	}

	printf("%d\n", getLargestSquare(H, W));

	return 0;
}


Measured memory_bytes: 17992
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<queue>
using namespace std;
#define int long  long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
signed main()
{
	int N;
	cin >> N;
	vector<int>L(N);
	int sum = 0, maxnum = 0;
	rep(i, N)
	{
		cin >> L[i];
		sum += L[i];
		maxnum = max(maxnum, L[i]);
	}
	if (maxnum < sum - maxnum)cout << "Yes";
	else cout << "No";
}

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

const int maxn=int(1e5)+100;

struct sblock 
{
	int x, y;

	bool operator < (const sblock b) const
	{
		return y<b.y;
	}
};

int n, m;
sblock block[maxn];

void read()
{
	scanf("%d%d", &n, &m);
	for (int i=1; i<=m; ++i)
	{
		scanf("%d%d", &block[i].x, &block[i].y);
		block[i].y--;
	}
}
void solve()
{
	sort(block+1, block+1+m);
	int ans=0;
	for (int i=1, pv=0; i<=m; ++i)
		if (pv<block[i].x)
		{
			++ans;
			pv=block[i].y;
		}
	printf("%d\n", ans);
}
int main()
{
	read();
	solve();
	return 0;
}

Measured memory_bytes: 1024
/*
 * src.cpp
 *
 *  Created on: 2016/08/04
 *      Author: joi
 */

#include <bits/stdc++.h>

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

using namespace std;

const int MAX_M=1e3,MAX_N=1e4;

int m,n;

char S[MAX_N][256];
char s[256];

bool flg[MAX_M];
vector<int> out;

bool numchk(){
	int len=strlen(s);
	REP(i,len){
		if (s[i]<'0' || s[i]>'9'){
			return false;
		}
	}
	return true;
}

int cnt(){
	int res=0;
	REP(i,m){
		if (flg[i]){
			res++;
		}
	}
	return res;
}

int main(){
	do{
		scanf("%d %d",&m,&n);
		if (m || n){
			memset(flg,1,sizeof(flg));
			REP(i,n){
				scanf("%s",S[i]);
			}
			int p=0;
			FOR(i,1,n+1){
				strcpy(s,S[i-1]);
				if (i%3==0 || i%5==0){
					if (i%15==0 && strcmp(s,"FizzBuzz")!=0){
						flg[p]=false;
					}
					if (i%3==0 && i%5!=0 && strcmp(s,"Fizz")!=0){
						flg[p]=false;
					}
					if (i%5==0 && i%3!=0 && strcmp(s,"Buzz")!=0){
						flg[p]=false;
					}
				}else{
					if (!numchk()){
						flg[p]=false;
					}
					int ans=atoi(s);
					if (i!=ans){
						flg[p]=false;
					}
				}
				p++;
				p%=m;
				while (!flg[p]){
					p++;
					p%=m;
				}
				if (cnt()==1){
					break;
				}
			}
			out.clear();
			REP(i,m){
				if (flg[i]){
					out.push_back(i+1);
				}
			}
			REP(i,(int)out.size()){
				if (i) printf(" ");
				printf("%d",out[i]);
			}
			printf("\n");
		}
	}while (n || m);
	return 0;
}

Measured memory_bytes: 3732
#include <bits/stdc++.h>
#define rep(i, n) for (ll(i) = 0; (i) < (n); (i)++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
int main()
{
    string s;
    cin >> s;
    int a, k;
    for (int i = 0; i < (1 << 3); i++)
    {
        a = s[0] - '0';
        k = 1;
        for (int j = 0; j < 3; j++)
        {
            if (i & (1 << j))
            {
                a += (s[k] - '0');
            }
            else
            {
                a -= (s[k] - '0');
            }
            k++;
        }
        if (a == 7)
        {
            k = 1;
            cout << s[0];
            for (int j = 0; j < 3; j++)
            {

                if (i & (1 << j))
                {
                    cout << "+";
                }
                else
                {
                    cout << "-";
                }
                cout << s[k];
                k++;
            }
            cout << "=7" << endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 256
// 失敗するからこそ そこから立ち向かって行く強さがあってそんな強さが本当の強さだと私は思うから
#ifdef DAIJOBU
#include "/home/v-o_o-v/deb.h"
#define deb(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#include <bits/stdc++.h>
#define deb(x...)
#endif 

using namespace std;

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef long long lint;
typedef double ld;

void a();void b();void c();void d();void e();void f();

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

	a();
	// b();
	// c();
	// d();
	// e();
	// f();
	return 0;
}

void a(){
	string s;
	cin >> s;
	if(s == "ABC")puts("ARC");
	else puts("ABC");
}

void b(){

}

void c(){

}

void d(){

}

void e(){

}

void f(){

}


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

typedef long long LL;
#define lowbit(x) ((x)&(-x))
#define INF 0x3f3f3f3f
#define memset(a,b) memset(a,b,sizeof(a))
#define	GE() printf(">----------\n")
#define	IN() freopen("in.txt","r",stdin)
#define	OUT() freopen("out.txt","w",stdout)
const LL mod=1000000007;
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const double eps=1e-8;
const int maxn=100005;

int n, fa[maxn], cnt;

struct edge{
    int u, v, cost;
    edge(int cu, int cv, int ccost){u=cu, v=cv, cost=ccost;}
    edge(){}
    bool operator<(const edge &cmp) const{
        return cost<cmp.cost;
    }
}E[maxn*4];

struct point{
    int x, y, id;
}P[maxn];;

bool cmpx(point c1, point c2){return c1.x<c2.x;}

bool cmpy(point c1, point c2){return c1.y<c2.y;}

int Find(int x){
    return x==fa[x]?x:fa[x]=Find(fa[x]);
}

LL Kruskal(){
    for(int i=0;i<=n;i++)fa[i]=i;
    sort(E, E+cnt);
    LL ans=0;
    for(int i=0;i<cnt;i++){
        int fu=Find(E[i].u);
        int fv=Find(E[i].v);
        if(fu!=fv){
            ans+=E[i].cost;
            fa[fu]=fv;
        }
    }
    return ans;
}

int main()
{
    while(~scanf("%d", &n)){
        for(int i=0;i<n;i++){
            scanf("%d%d", &P[i].x, &P[i].y);
            P[i].id=i;
        }
        cnt=0;
        sort(P, P+n, cmpx);
        for(int i=1;i<n;i++){
            E[cnt++]=edge(P[i-1].id, P[i].id, P[i].x-P[i-1].x);
        }
        sort(P, P+n, cmpy);
        for(int i=1;i<n;i++){
            E[cnt++]=edge(P[i-1].id, P[i].id, P[i].y-P[i-1].y);
        }
        printf("%lld\n", Kruskal());
    }
    return 0;
}


Measured memory_bytes: 6528
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct Node{
  int key;
  struct Node *l;
  struct Node *r;
  struct Node *p;
};

typedef struct Node *node;

void insert(node,node);
void inorder(node);
void preorder(node);

int main(){

  node root,T[500000];
  int i,m,num;
  char str[7];

  scanf("%d",&m);
  root=(node)malloc(sizeof(struct Node));

  for(i=0;i<m;i++){
    T[i]=(node)malloc(sizeof(struct Node));
    scanf("%s",str);
    if(strcmp(str,"insert")==0){
      scanf("%d",&T[i]->key);
      T[i]->r=NULL;
      T[i]->l=NULL;
      insert(root,T[i]);
    }else if(strcmp(str,"print")==0){
      inorder(T[0]);
      printf("\n");
      preorder(T[0]);
      printf("\n");

    }
  }


  return 0;
}

void insert(node root,node z){

 node x,y;

  y = NULL; // x ??????
  x = root;
  while( x != NULL){
    y = x; // ???????¨????
    if (z->key < x->key){
      x = x->l; // ?????????????§????
    } else{ 
      x = x->r; // ?????????????§????
    }
  }
  z->p = y;

  if( y == NULL){ // T ???????????´???
    root = z;
  }else if( z->key < y->key){
    y->l = z; // z ??? y ?????????????????????
  }else{ 
    y->r = z; // z ??? y ?????????????????????

  }
}
void inorder(node T){
  if(T==NULL)return;
  inorder(T->l);
  printf(" %d",T->key);
  inorder(T->r);
}
void preorder(node T){
  if(T==NULL)return;
  printf(" %d",T->key);
  preorder(T->l);
  preorder(T->r);
}

Measured memory_bytes: 27944
'use strict';
process.stdin.on('data', function(chunk) {
    var inputs = chunk.toString().trim();
  var r = Number(inputs);
    console.log(
  	Math.PI * Math.pow(r,2)
  	, 2 * Math.PI * r
  	);
  });
process.stdin.resume();
process.stdin.setEncoding('utf8');

Measured memory_bytes: 15576
#include<stdio.h>
#include<vector>
using namespace std;

vector<int> v;

void pushBack(int _x){
    v.push_back(_x);
}

void randomAccess(int _x){
    printf("%d\n", v[_x]);
}

void popBack(){
    v.pop_back();
}

int main(){

    v.reserve(100000);
    int q;
    scanf("%d", &q);

    for(int i=0; i<q; i++){
        int x;
        scanf("%d", &x);

        if(x==0){
            int _x;
            scanf("%d", &_x);
            pushBack(_x);
        }else if(x==1){
            int _x;
            scanf("%d", &_x);
            randomAccess(_x);
        }else if(x==2){
            popBack();
        }
    }
    return 0;
}


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

using namespace std;

#define ll long long int
#define get(a) ll a; cin >> a;
#define show(a) cout << a << endl;
#define full(p) p.begin(), p.end()
#define sz(a) (ll)(a.size())
#define pb push_back

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.precision(10);
	cout<<fixed;
	////////////////////////////////
	get(a);
	get(b);
	get(c);

	cout << min(c, b/a) << endl;	

	return 0;
}

Measured memory_bytes: 3616
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
dist = 0
for x1, y1 in XY:
    for x2, y2 in XY:
        dist += ((x1 - x2)**2 + (y1 - y2)**2)**(1/2)
print(dist/N)


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

int main(){
  int n;
  cin >> n;
  vector<double> a(n);
  for(int i=0;i<n;i++){
    cin >> a.at(i);
  }
  double ans =0;
  sort(a.begin(),a.end());
   for(int i=0;i<n-1;i++){
     a.at(0) = (a.at(0)+a.at(i+1))/2;
   }
  cout << a.at(0) << endl;
  }

Measured memory_bytes: 256
package main

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

var sc = bufio.NewScanner(os.Stdin)

func Scan() string {
	sc.Scan()
	return sc.Text()
}
func iScan() int {
	n, _ := strconv.Atoi(Scan())
	return n
}
func fScan() float64 {
	n, _ := strconv.ParseFloat(Scan(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func SScan(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scan()
	}
	return a
}
func iSScan(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = iScan()
	}
	return a
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}
func larger(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}
func smaller(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
func max(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x < a[i] {
			x = a[i]
		}
	}
	return x
}
func min(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x > a[i] {
			x = a[i]
		}
	}
	return x
}
func sum(a []int) int {
	x := 0
	for _, v := range a {
		x += v
	}
	return x
}

var mod int = 1000000007

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	n := iScan()
	h := iSScan(n)
	ans := 0
	for {
		idx := make([]int, 0, n)
		if h[0] != 0 {
			ans++
			idx = append(idx, 0)
		}
		for i := 1; i < n; i++ {
			if h[i-1] == 0 && h[i] != 0 {
				ans++
			}
			if h[i] != 0 {
				idx = append(idx, i)
			}
		}
		for _, v := range idx {
			h[v]--
		}
		c := 0
		for _, v := range h {
			if v == 0 {
				c++
			}
		}
		if c == n {
			break
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 1868
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define Yes                \
    cout << "Yes" << endl; \
    return 0;
#define No                \
    cout << "No" << endl; \
    return 0;
using namespace std;
using ll = long long;
const int INF = 1001001001;
const int MOD = 1000000007;
typedef long long ll;

template <typename T>
void print(const T &v);

int main()
{
    int N, A, B;
    cin >> N >> A >> B;
    cout << min(N * A, B) << endl;
    return 0;
}

// Use For Debug
template <typename T>
void print(T const &v)
{
    for (int i = 0; i < v.size(); i++)
    {
        if (i)
            cout << " ";
        cout << v[i];
    }
    cout << endl;
}


Measured memory_bytes: 384
import java.util.*;
import java.math.RoundingMode;
import java.math.BigDecimal;
 
 
public class Main{
	public static void main (String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int k = sc.nextInt();
		long[] a = new long[n + 1];
		long[] b = new long[m + 1];
		for (int i = 1; i <= n; i++) {
			a[i] = a[i - 1] + sc.nextInt();
		}
		for (int i = 1; i <= m; i++) {
			b[i] = b[i - 1] + sc.nextInt();
		}
      
		int max = 0;
		for (int i = 0, j = m; i <= n; i++) {
			while (j >= 0 && k < a[i] + b[j]) j--;
			if (j < 0) break;
			max = Math.max(max, i + j);
		}
		System.out.println(max);
	}
}

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

int main(){
	int x,y;
	while(1){
		cin>>x>>y;
		if(x==0 && y==0)
			break;
		if(x<y)
			cout<<x<<" "<<y<<endl;
		else
			cout<<y<<" "<<x<<endl;
	}
	return 0;
}

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

int main(){
		int n,total=0 ;
  		cin>>n;
  		
		total = n + total;
    	total = (n*n) + total;
  		total = (n*n*n) + total;
  
  		
  		cout<<total;
		
	}

Measured memory_bytes: 3624
N = int(raw_input())
a = map(int, raw_input().split())
ans = 0
i = 0
while i < N-1:
  if a[i] == a[i+1]:
    if i+2 < N and a[i] == a[i+2]:
      a[i+1] = 101+ans
    else:
      a[i] = 101+ans
    ans += 1
    i += 2
  else:
    i += 1
print ans



Measured memory_bytes: 2568
#include <bits/stdc++.h>
using namespace std;
struct Fast { Fast() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20);} } fast;
 
int main() {
    int n, sum = 0;
    cin >> n;
    vector<int>h(n + 1);
    for (int i = 1; i < n + 1; i++){
        cin >> h[i];
        if (h[i - 1] <= h[i]){
          sum = sum + h[i] - h[i - 1];
        }
    }
    cout << sum << endl;
}

Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Denis Nedelyaev
 */
public class Main {
    public static void main(String[] args) throws Exception {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        AtB solver = new AtB(in, out);
        solver.solve(1);
        out.close();
    }

    static class AtB {
        private final FastScanner in;
        private final PrintWriter out;

        public AtB(FastScanner in, PrintWriter out) {
            this.in = in;
            this.out = out;
        }

        public void solve(int testNumber) {
            int k = in.nextInt();
            int t = in.nextInt();
            int[] a = in.nextInts(t);

            int max = 0;
            for (int i = 0; i < t; i++) {
                max = Math.max(max, a[i]);
            }

            int p = k / 2;
            int q = k - p;

            if (max > q) {
                int x = max - q;
                if (k % 2 == 1) {
                    out.println(2 * x);
                } else {
                    out.println(2 * x - 1);
                }
            } else {
                out.println(0);
            }
        }

    }

    static class FastScanner {
        private final static int BUFFER_SIZE = 4096;
        private final InputStream in;
        private byte[] buffer = new byte[BUFFER_SIZE];
        private int pos = 0;
        private int size;

        public FastScanner(InputStream inputStream) throws IOException {
            in = inputStream;
            size = 0;
        }

        public int nextInt() {
            int c = skipWhitespace();

            int sign = -1;
            if (c == '-') {
                sign = 1;
                c = read();
            }

            int ans = 0;

            while (c > ' ') {
                ans *= 10;
                ans -= c - '0';
                c = read();
            }

            return sign * ans;
        }

        public int[] nextInts(int n) {
            int[] res = new int[n];
            for (int i = 0; i < n; i++) {
                res[i] = nextInt();
            }
            return res;
        }

        private int skipWhitespace() {
            while (true) {
                int c = read();
                if (c > ' ' || c == -1) {
                    return c;
                }
            }
        }

        private int read() {
            if (pos >= size) {
                try {
                    size = in.read(buffer, 0, BUFFER_SIZE);
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
                if (size <= 0) {
                    return -1;
                }
                pos = 0;
            }
            return buffer[pos++];
        }

    }
}



Measured memory_bytes: 8404
#include<iostream>
#include<stdio.h>
using namespace std;

int main(void){

  int num,i;
  i = 1;
  
  while(cin >> num){
    if(num == 0) break;
    printf("Case %d: %d\n",i,num);
    i++;
  }
  return 0;
}

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

int main(){
    string s;
    cin >> s;
    if ((s[0]==s[1] && s[1]==s[2]) || (s[1]==s[2] && s[2]==s[3]))
        cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
var
a:array[0..55,0..55] of char;
n,m,i,j,s:longint;
begin
readln(n,m);
for i:=1 to n do
  begin
    for j:=1 to m do read(a[i,j]);
    readln;
  end;
for i:=0 to m+1 do begin a[0,i]:=' ';a[n+1,i]:=' ';end;
for i:=1 to n do begin a[i,0]:=' ';a[i,m+1]:=' ';end;
for i:=1 to n do
  begin
    for j:=1 to m do
      if a[i,j]='.' then
        begin
          s:=0;
          if a[i-1,j-1]='#' then inc(s);
          if a[i-1,j]='#' then inc(s);
          if a[i-1,j+1]='#' then inc(s);
          if a[i,j-1]='#' then inc(s);
          if a[i,j+1]='#' then inc(s);
          if a[i+1,j-1]='#' then inc(s);
          if a[i+1,j]='#' then inc(s);
          if a[i+1,j+1]='#' then inc(s);
          write(s);
        end
        else write(a[i,j]);
    writeln;
  end;
end.

Measured memory_bytes: 128
import sys
n=int(sys.stdin.readline())
arr=list(map(int,sys.stdin.readline().split()))
from collections import defaultdict
s=0
dic=defaultdict(int)
for i in range(n):
    dic[arr[i]]+=1
for i in dic:
    s+=(dic[i]*(dic[i]-1))//2
#print(s,'s')
for i in range(n):
    a=arr[i]
    ans=s
    
    ans-=dic[a]*(dic[a]-1)//2
    if dic[a]-2>=0:
        ans+=(dic[a]-1)*(dic[a]-2)//2
    print(ans)


Measured memory_bytes: 85068
N=int(input())
T, A=map(int, input().split())
H=input().split()
V=[abs(T-0.006*int(h)-A) for h in H]

minv = V[0]
index=0

for i,v in list(enumerate(V)):
    if v<minv:
        minv=v
        index=i

print(index+1)
        
    

Measured memory_bytes: 3188