akhauriyash/Code-Regression huggingface dataset:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    A, B, N = MI()

    if N < B:
        x = N
    else:
        x = B - 1
    print(floor(A * x / B))

if __name__ == '__main__':
    solve()


Measured memory_bytes: 9168
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a[3];
	scanf("%d%d%d",&a[0],&a[1],&a[2]);
	sort(a,a+3);
	if(a[0]==5&&a[1]==5&&a[2]==7){
		cout<<"YES";
	}		
	else{
		cout<<"NO";	
	}
	return 0;
}

Measured memory_bytes: 256
n = gets.chomp.to_i
a = gets.chomp.split(" ").map(&:to_i)
h = Hash.new(0)
ans = 0

n.times do |i|
    li = i + a[i]
    ri = i - a[i]
    h[li] += 1
    ans += h[ri] if h.has_key?(ri)
end

puts ans

Measured memory_bytes: 38776
//In the name of God
#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N = 2e5 + 10 , MOD = 1e9 + 7;
int n , m , a , b , fact[N] , ifact[N];
int powmod(int x , int y){
        int ret = 1;
        for(; y ; y>>=1){
                if(y&1)
                        ret = ret * x % MOD;
                x = x * x % MOD;
        }
        return ret;
}

int C(int r , int n){
        if(r < 0 || n < 0 || r > n)
                return 0;
        int ret = fact[n];
        ret = ret * ifact[r] % MOD;
        ret = ret * ifact[n-r] % MOD;
        return ret;
}

int32_t main(){
        fact[0] = 1;
        ifact[0] = 1;
        for(int i=1 ; i < N ; i++){
                fact[i] = i * fact[i-1] % MOD;
                ifact[i] = powmod(fact[i] , MOD-2);
        }
        cin >> n >> m >> a >> b;
        if(a == n || b == m)
                return cout << 0 , 0;
        int res = 0;
        for(int i=b+1 ; i <= m ; i++){
                res += C(i-1 , i-1 + n - a-1) * C(m-i , m-i + a-1) % MOD;
                res %= MOD;
        }
        cout << res;
        return 0;
}       


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

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

    int food[m];
    fill(food, food + m, 0);

    for (int i = 0; i < n; i++) {
        int k;
        cin >> k;
        for (int j = 0; j < k; j++) {
            int x;
            cin >> x;
            --x;
            ++food[x];
        }
    }
    int res = 0;
    for (int i = 0; i < m; i++) {
        if (food[i] == n) ++res;
    }

    cout << res << endl;
}


Measured memory_bytes: 256
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif

#define sz(x) ((int) (x).size())
#define TASK "text"

const int inf = (int) 1.01e9;
const long long infll = (long long) 1.01e18;
const ld eps = 1e-9;
const ld pi = acos((ld) -1);

mt19937 mrand(random_device{} ()); 

int rnd(int x) {
  return mrand() % x;
}

const int mod = (int) 1e9 + 7;

int mul(int a, int b) {
  return (long long) a * b % mod;
}

void add(int &a, int b) {
  a += b;
  if (a >= mod) {
    a -= mod;
  }
}

const int maxn = (int) 1e5 + 5;
int f[maxn], inv[maxn];

void precalc() {
  f[0] = 1;
  for (int i = 1; i < maxn; i++) {
    f[i] = mul(f[i - 1], i);
  }
  inv[1] = 1;
  for (int i = 2; i < maxn; i++) {
    inv[i] = (mod - (long long) (mod / i) * inv[mod % i] % mod) % mod;
  }
}

int n;
int a[maxn];

int read() {
  if (scanf("%d", &n) < 1) {
    return false;
  }
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }
  return true;
}

int b[maxn];

int get1(int s, int k) {
  int res = 0;
  {
    int x = b[k];
    int suff = b[n];
    add(suff, mod - b[n - k]);
    add(x, suff);
    add(res, mul(x, inv[k + 1]));
    add(s, mod - x);
  }
  add(res, mul(mul(s, 2), mul(inv[k + 1], inv[k + 2])));
  return res;
}

void solve() {
  if (n == 1) {
    printf("%d\n", a[0]);
    return;
  }
  b[0] = 0;
  for (int i = 0; i < n; i++) {
    b[i + 1] = b[i];
    add(b[i + 1], a[i]);
  }
  int s = b[n];
  int res = get1(s, 1);
  for (int i = 1; i + 1 < n; i++) {
    int suff = b[n];
    add(suff, mod - b[n - i]);
    add(s, mod - suff);
    int toadd = b[n];
    add(toadd, mod - b[i]);
    add(s, toadd);
    add(res, get1(s, i + 1));
  }
  add(res, b[n]);
  res = mul(res, f[n]);
  printf("%d\n", res);
}

int main() {
  precalc();
#ifdef DEBUG
  assert(freopen(TASK ".in", "r", stdin));
  assert(freopen(TASK ".out", "w", stdout));
#endif
  while (read()) {
    solve();
#ifdef DEBUG
    eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define pi acos(-1.0)
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
 
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) c.begin(), c.end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int main(){
    int n;
    cin >> n;
    VL a(3*n);
    REP(i,3*n) scanf("%lld", &a[i]);
    VL form(n+1), lat(n+1);
    priority_queue<ll, VL, greater<ll> > pq;
    ll s = 0;
    REP(i,n){
        s += a[i];
        pq.push(a[i]);
    }
    form[0] = s;
    FOR(i,n,2*n-1){
        ll x = pq.top();
        if (a[i] > x){
            pq.pop();
            pq.push(a[i]);
            s += a[i] - x;
        }
        form[i-n+1] = s;
    }

    priority_queue<ll> pq2;
    s = 0;
    FORR(i,3*n-1,2*n){
        s += a[i];
        pq2.push(a[i]);
    }
    lat[0] = s;
    FORR(i,2*n-1,n){
        ll x = pq2.top();
        if (a[i] < x){
            pq2.pop();
            pq2.push(a[i]);
            s += a[i] - x;
        }
        lat[2*n-i] = s;
    }
    reverse(ALL(lat));

    ll ans = -1e18;
    REP(i,n+1){
        // printf("%lld %lld\n", form[i], lat[i]);
        ans = max(ans, form[i] - lat[i]);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 6516
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

using namespace std;
using ll = long long;
using P = pair<int, int>;


int main() {
	int s, t,c;
	string a, b;
	cin >> a >> b;
	vector<int>p;
	s = a.size();
	t = b.size();
	rep(i, s - t+1) {
      c=t;
		rep(j, t) {
			if (a[i + j] ==b[j] ) {
				c=c-1;
			}
		}
		p.push_back(c);
	}
	sort(p.begin(), p.end());
	cout<<p[0]<<endl;
	return 0;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
#define pii pair<ll,ll>
#define vi vector<ll>
#define vs vector<string>
#define vii vector<pii>
#define mi map<ll,ll>
#define mii map<pii,ll>
#define mc map<char,ll>
#define itr ::iterator
#define f(i,a,b) for(ll i=a;i<b;i++)
#define fe(i,a,b) for(ll i=a;i<=b;i++)
#define fn(i,a,b) for(ll i=a;i>b;i--)
#define fne(i,a,b) for(ll i=a;i>=b;i--)
#define fm(it,m) for(it = m.begin();it != m.end();++it)
#define all(v) v.begin(),v.end()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define M 1000000007
#define pi 3.14159265358979323846

char grid[1005][1005];
long long int dp[1005][1005];
int n=0,m=0;

long long int solve(int i,int j)
{ 
  if(i>n-1 || j>m-1)
    return 0;

  if(grid[i][j]=='#')
    return dp[i][j]=0;

  if(dp[i][j]!=-1)
    return dp[i][j];

  if(i==n-1 && j==m-1)
    return dp[i][j]=1;

  return dp[i][j] = ((solve(i+1,j))%M + (solve(i,j+1))%M)%M;
}

int main()
{  
      IOS;
      cin>>n>>m;
      
      f(i,0,n)
       {
        f(j,0,m)
         {
          cin>>grid[i][j];
          dp[i][j]=-1;
         }
       }

      solve(0,0);
      cout<<dp[0][0];
     
  return 0;
}


Measured memory_bytes: 12544
import sys
rs = lambda: sys.stdin.readline().rstrip()
ri = lambda: int(rs())
rs_ = lambda: [_ for _ in rs().split()]
ri_ = lambda: [int(_) for _ in rs().split()]

N, M = ri_()
if N == 1 and M == 1:
    print(1)
elif N == 1:
    print(M - 2)
elif M == 1:
    print(N - 2)
else:
    print((N - 2) * (M - 2))

Measured memory_bytes: 38256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;

const int N=16;
const int M=32805;

int n,m,x,y,w,sum,sz;
int f[N][N],dp[M][N],cst[M];

int main(){
	int i,j,k,s,ss,all;
	scanf("%d%d",&n,&m); sz=(1<<n)-1;
	for (i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&w);
		f[x][y]=f[y][x]=w;
		sum+=w;
	}
	memset(dp,-1,sizeof(dp));
	for (i=1;i<=sz;i++){
		for (k=1;k<=n;k++)
			if ((i>>k-1)&1) break;
		cst[i]=cst[i^(1<<k-1)];
		for (j=k+1;j<=n;j++)
			if ((i>>j-1)&1) cst[i]+=f[j][k];
		if (k==1) dp[i][1]=cst[i];
	}
	for (s=1;s<=sz;s++){
		for (i=1;i<=n;i++){
			if (dp[s][i]==-1) continue;
			for (j=1;j<=n;j++){
				if ((s>>j-1)&1) continue;
				if (!f[i][j]) continue;
				dp[s^(1<<j-1)][j]=max(dp[s^(1<<j-1)][j],dp[s][i]+f[i][j]);
				for (ss=all=sz^s^(1<<j-1);ss;ss=(ss-1)&all)
					dp[s^(1<<j-1)^ss][j]=max(dp[s^(1<<j-1)^ss][j],dp[s][i]+f[i][j]+cst[ss^(1<<j-1)]);
			}
		}
	}
	printf("%d\n",sum-dp[sz][n]);
	return 0;
}

Measured memory_bytes: 2432
//Depth First Search
#include <iostream>
#include <vector>

using namespace std;

static const int N = 100;
static const int WHITE = 0;
static const int BLACK = 1;

int color[N] = {WHITE}, d[N] = {}, f[N] = {}, tt = 1;

void dfs(vector<vector<int>> &graph, int u) {
    if(color[u] == BLACK) return;
    color[u] = BLACK;
    d[u] = tt++;
    for(auto v: graph[u]) dfs(graph, v);
    f[u] = tt++;
}

int main() {
    int n;
    cin >> n;
    int u, k, v;
    vector<vector<int>> graph(n);
    for(int i=0; i<n; i++) {
        cin >> u >> k;
        u--;
        for(int j=0; j<k; j++) {
            cin >> v;
            v--;
            graph[u].push_back(v);
        }
    }

    for(int i = 0; i < n; i++)
        dfs(graph, i);

    for(int i = 0; i < n; i++)
        cout << i+1 << " " << d[i] << " " << f[i] << endl;
    return 0;
}



Measured memory_bytes: 3116
let get_3_ints () = Scanf.scanf "%d %d %d" (fun u v w -> u,v,w)
let range ?(stride=1) u v =
  let rec f0 i a = if i>v then a else f0 (i+stride) (i::a)
  in f0 u []
let char_list_of_string str = 
  let rec f0 i a =
    if i<0 then a else f0 (i-1) (str.[i]::a)
  in f0 (String.length str - 1) []

let () =
  let (n,a,b) = get_3_ints ()
  in
  range 1 n
  |> List.fold_left (fun u v ->
    (* Printf.printf "%d\n" v; *)
    v
    |> string_of_int
    |> char_list_of_string
    |> List.fold_left (fun u v -> u + (int_of_char v) - (int_of_char '0')) 0
    |> (fun k ->
      (* Printf.printf "  %d\n" k; *)
      if a<=k && k<=b then u+v else u
    )) 0
  |> Printf.printf "%d\n"

Measured memory_bytes: 2048
#include <string>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <iostream>
#include <functional>
#include <algorithm>
#include <sstream>
#include <iterator>
#include <cmath>

using namespace std;
typedef long long ll;

int main()
{
	int N;
	cin >> N;
	int odd = 0;
	for (int i = 0; i < N; i++) {
		int A;
		cin >> A;
		if (A % 2 != 0)
			odd++;
	}
	cout << ((odd % 2 == 0) ? "YES" : "NO") << endl;
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void){
    int W,H,x,y,r;
    scanf("%d %d %d %d %d",&W,&H,&x,&y,&r);
    if((x+r<=W&&0<=x-r)&&(y+r<=H&&0<=y-r)){
        printf("Yes\n");
    }
    else{
        printf("No\n");
    }
    return 0;
}


Measured memory_bytes: 2112
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace AtCoder.B
{
    public class Program
    {
        public static void Main() { var r = GetResult(); Debug.WriteLine(r); Console.Write(r); }

        private static object GetResult()
        {
            var N = ReadLong();
            var zoroCount = 0;
            for (int i = 0; i < N; i++)
            {
                var (D1, D2) = Read2Longs();
                if (D1 == D2)
                {
                    zoroCount++;
                    if (zoroCount == 3) return "Yes";
                }
                else
                {
                    zoroCount = 0;
                }
            }
            return "No";
        }

        #region Console.Read

        public static string ReadText() { return Console.ReadLine(); }
        public static List<string> ReadTexts() { return Console.ReadLine().Split(' ').ToList(); }
        public static long ReadLong() { return long.Parse(Console.ReadLine()); }
        public static (long, long) Read2Longs() { var ls = ReadLongs(); return (ls[0], ls[1]); }
        public static (long, long, long) Read3Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2]); }
        public static (long, long, long, long) Read4Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2], ls[3]); }
        public static (long, long, long, long, long) Read5Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2], ls[3], ls[4]); }
        public static List<long> ReadLongs() { return Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToList(); }

        #endregion
    }
}


Measured memory_bytes: 28292
//#include "pch.h"
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

#define FOR(i, s, e) for(int i=s; i<e; i++)
#define REF(i, s, e) for(int i=s; i>e; i--)
typedef long long ll;

int n;
vector<int> H(21);

bool judge(int index){
    if (index == 0) return true;
    
    FOR(i,0,index){
        if (H[i] > H[index]) return false;
    }
    return true;
}

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
    cin >> n;
    
    FOR(i,0,n){
        cin >> H[i];
    }
    
    //cout << "H:" << endl;
    //FOR(i,0,n) cout << H[i] << endl;
    
    //0~iまででHiがmaxなら海見える
    int count = 0;
    FOR(i,0,n){
        //cout << judge(i) << endl;
        if (judge(i)) count++;
    }
    
    cout << count << endl;
}

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

using namespace std;

struct UnionFind
{
  vector< int > data;

  UnionFind(int sz) : data(sz, -1) {}

  int find(int k)
  {
    return (data[k] < 0 ? k : data[k] = find(data[k]));
  }

  void unite(int x, int y)
  {
    x = find(x);
    y = find(y);
    if(x == y) return;
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
  }

  int size(int k)
  {
    return (-data[find(k)]);
  }
};

int main()
{
  int V;
  string S[1000];
  cin >> V;
  UnionFind tree(V);
  int all = V * (V - 1) / 2;
  for(int i = 0; i < V; i++) {
    cin >> S[i];
    for(int j = 0; j < i; j++) {
      if(S[i][j] == 'Y') tree.unite(i, j), --all;
    }
  }
  int sz[2] = {};
  for(int i = 0; i < V; i++) {
    if(tree.find(i) == i) sz[tree.size(i) % 2]++;
  }
  if(all % 2 == 0) {
    if(sz[0] <= 1 && sz[1] == 2) cout << "Taro" << endl;
    else cout << "Hanako" << endl;
  } else {
    if(sz[0] == 0 && sz[1] == 2) cout << "Hanako" << endl;
    else cout << "Taro" << endl;
  }
}

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

char c[2][3];

int main(){
	for(int i = 0;i < 2;i++){
		for(int j = 0;j < 3;j++){
			cin >> c[i][j];
		}
	}

	if(c[0][0]==c[1][2] && c[0][1]==c[1][1] && c[0][2]==c[1][0])cout << "YES" << endl;
	else cout << "NO" << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <complex>
#include <vector>
#include <deque>
#include <queue>
#include <list>
#include <stack>
#include <string>
#include <functional>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <cstdlib>

#define rep(i, b) for(int i = 0; i < b; i++)
#define repi(i, a, b) for(int i = a; i < b; i++)
#define all(c) c.begin(),c.end()
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define MAX_V 1001
#define MAX_E 401
#define INF INT_MAX
#define MOD 1000000007
#define EPS 1e-7
typedef long long ll;
inline int toInt(std::string s) { int v; std::istringstream sin(s); sin >> v; return v; }
template<class T> inline std::string toString(T x) { std::ostringstream sout; sout << x; return sout.str(); }
using namespace std;

typedef double D;      // 座標値の型。doubleかlong doubleを想定
typedef complex<D> P;  // Point
typedef pair<P, P> L;  // Line
#define X real()
#define Y imag()
typedef pair<int, int> pii;

int main()
{
	string a;
	rep(i, 3)
	{
		cin >> a;
		cout << a[i];
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 256
#include <ext/pb_ds/assoc_container.hpp>
#include <bits/stdc++.h>
using namespace std;
using namespace __gnu_pbds;
template <class c, class cmp = less<c> > using ordered_set = tree<c, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...) 
#endif
template<class T> ostream& operator<<(ostream &os, vector<T> V) {os << "[ "; for(auto v : V) os << v << " "; return os << "]";}
template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P) {return os << "(" << P.first << "," << P.second << ")";}
template <typename T,typename U>pair<T,U> operator+(const pair<T,U> & l,const std::pair<T,U> & r) { return {l.first+r.first,l.second+r.second};}
typedef long long int ll;
const ll mod =998244353;
const int maxn = 200005;
#define endl '\n'
#define ld long double
#define int ll
#define all(x) (x).begin(),(x).end()


int32_t main()
{ 
  IOS
 
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i = 0;i<n;i++) cin >> a[i];
  sort(all(a));
  int ans = 0;
  for(int i= 0;i<n;i++){
    for(int j = i+1;j<n;j++){
      for(int k =  j+1;k<n;k++){
        if(a[i]+a[j] > a[k] and (a[i]!=a[j]) and (a[i]!=a[k]) and (a[j]!=a[k])){
          ans++;
        }
      }
    }
  }
  cout << ans<<endl;

  

  










  
    
} 



Measured memory_bytes: 3612
#include <algorithm>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <set>
#include <string>
#include <vector>
#define rep(i, x, n) for(int i = x; i < n; i++)
using namespace std;
const long long INF = 1LL << 60;
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
const int MOD = 1000000007;
int rui(int a, int b) {
    if(b == 0) {
        return 1;
    }
    return rui(a, b - 1) * a;
}
int main() {
    int A, B, C, K;
    cin >> A >> B >> C >> K;
    int bai = 1;
    rep(i, 0, K) { bai *= 2; }
    int m = max({A, B, C});
    cout << A + B + C - m + m * bai << endl;
}

Measured memory_bytes: 256
N,W=map(int,input().split())
w=[0]*(N+1)
v=[0]*(N+1)
for i in range(1,N+1):
  w[i],v[i]=map(int,input().split())

dp=[[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(1,N+1):
  for j in range(1,W+1):
    #print("i=",i,"j=",j)
    dp[i][j]=max(dp[i][j],dp[i-1][j])
    if j-w[i]<0: continue
    dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i])

#print(dp)
print(dp[N][W])


Measured memory_bytes: 171784
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0140

"""
import sys
from sys import stdin
input = stdin.readline



def solve(path, start, goal):
    path_a = [0]*100            #  ???????????????????????????
    path_b = [0]*100

    # ?????????????????¨??????????????????????????????????????°?????§??????????????¢???
    try:
        path_a = path[start][0][:path[start][0].index(goal)+1]
    except ValueError:
        pass
    try:
        path_b = path[start][1][:path[start][1].index(goal)+1]
    except ValueError:
        pass

    # ??????????????????????±???????????????????????????§???start??????goal?????§????????????????????§1??????????????????
    if len(path_a) < len(path_b):
        return ' '.join(map(str, path_a))
    else:
        return ' '.join(map(str, path_b))


def main(args):
    path = []                   #  ?????????n???????????????????????????????????????
    # ?????????[n]???????????????????????????????????????????????¨????????´?????¨??????????????????????????¨????????´????????°??????
    path.append([[0, 1, 2, 3, 4, 5, 6, 7, 8, 9], []])                #  0????????????
    path.append([[1, 2, 3, 4, 5, 6, 7, 8, 9, 5, 4, 3, 2], [1, 0]])   #  1
    path.append([[2, 3, 4, 5, 6, 7, 8, 9, 5, 4, 3, 2], [2, 1, 0]])   #  2
    path.append([[3, 4, 5, 6, 7, 8, 9, 5, 4, 3, 2], [3, 2, 1, 0]])   #  3
    path.append([[4, 5, 6, 7, 8, 9, 5, 4, 3, 2], [4, 3, 2, 1, 0]])   #  4
    path.append([[5, 6, 7, 8, 9, 5, 4, 3, 2], [5, 4, 3, 2, 1, 0]])   #  5
    path.append([[6, 7, 8, 9, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5], []]) #  6
    path.append([[7, 8, 9, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6], []]) #  7
    path.append([[8, 9, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 7], []]) #  8
    path.append([[9, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8], []]) #  9

    n = int(input())
    for _ in range(n):
        start, goal = map(int, input().split())
        result = solve(path, start, goal)
        print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

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

int data[1001000]={0};

int main(){
    int n,k;
    int sum = -10000000;
    int tmp;
    while(1){
        cin >> n >> k;
        tmp = 0;
        if(n == 0 && k == 0) break;
        for(int i=0;i<n;i++) cin >> data[i];
        for(int i=0;i<k;i++) tmp += data[i];
        sum = max(sum,tmp);
        for(int i=k;i<n;i++){
            tmp -= data[i-k];
            tmp += data[i];
            sum = max(tmp,sum);
        }
        cout << sum << endl;
    }
}

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

int main()
{
    int n;cin>>n;
    ll ans=1;
    vector<ll>a(n);
    for(int i=0;i<n;++i){
        cin>>a[i];
    }
    sort(a.begin(),a.end());
    for(int i=0;i<n;++i){
        if(a[i]==0){
            ans=0;
            break;
        }
        if((ll)1e18/a[i] < ans){
            ans=-1;
            break;
        }
        ans*=a[i];
    }
    cout<<ans;
}

Measured memory_bytes: 4048
import java.util.*;
public class Main{
    static long[][] dp = new long[1000000][3];
	public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        long[][] a = new long[1000000][3];
        int n = sc.nextInt();
        for(int i=0; i<n; i++)
        for(int j=0; j<3; j++) a[i][j] = sc.nextInt();

        for(int i=0; i<n; i++){
            for(int j=0; j<3; j++){
                for(int k=0; k<3; k++){
                    if(j==k) continue;
                    dp[i+1][k] = Math.max(dp[i][j]+a[i][k],dp[i+1][k]);
                }
            }
        }
        long ans = 0;
        for(int j = 0; j<3; j++) ans = Math.max(ans,dp[n][j]);
        System.out.println(ans);
    }
    
}


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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl




typedef long long ll;
const ll mod = 1e9+7;
const int maxn = 1e6 + 5;




int n;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
    cin>>n;
    map<char,int> mp;

    string s; cin>>s;
    for (char c: s) {
	mp[c]++;
    }
    
    for (int i=1; i<n; i++) {
	map<char,int> freq;
	string s; cin>>s;
	for (char c: s) {
	    freq[c]++;
	}

	for (auto p: mp) {
	    mp[p.first] = min(mp[p.first], freq[p.first]);
	}
    }

    string res;
    for (auto p: mp) {
	for (int j=0;j<p.second;j++) res+=p.first;
    }
    out(res);  

    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int q = sc.nextInt();
        int[] a = new int[q];
        for (int i = 0 ; i < q ; i++) {
            a[i] = sc.nextInt();
        }

        int[] t = new int[n + 1];
        for (int i = 0 ; i < q ; i++) {
            if (a[i] != 1) {
                t[0]++;
                t[a[i] - 1]--;
            }
            if (a[i] != n) {
                t[a[i]]++;
                t[n]--;
            }

        }

        for (int i = 0 ; i < n ; i++) {
            if (0 < i) {
                t[i] += t[i - 1];
            }
        }


        for (int i = 0 ; i < n ; i++) {
            if (t[i] >= k) {
                System.out.println("No");
            } else {
                System.out.println("Yes");
            }
        }

    }

}

Measured memory_bytes: 57304
import numpy as np

N,M = [int(i) for i in input().split()]

cost = [0]*N

for i in range(N):
    a,b = [int(j) for j in input().split()]

    cost[i] = (a,b)

cost = sorted(cost,key=lambda x:x[0])
i = 0
cnt =0
money = 0

while cnt < M:
    a,b= cost[i]

    tmp = min(M - cnt,b)
    cnt += tmp
    money += a*tmp
    i += 1


print(money)

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

#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
const int INF = 1e9;

int main() {
  string s, t;
  cin >> s >> t;
  bool ok = true;
  rep(i, s.size()) if (s[i] != t[i]) ok = false;

  cout << (ok ? "Yes" : "No") << endl;
  return 0;
}


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

#define REPI(i, n) for(int i = 0; i < n; i++)
#define REPJ(j, n) for(int j = 0; j < n; j++)

using namespace std;

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

    int a, b; cin >> a >> b;
    if(a + b < 10) cout << a + b;
    else cout << "error";
}


Measured memory_bytes: 256
N, A, B, C, D = map(int, input().split())
S = str(input())

A -= 1
B -= 1
C -= 1
D -= 1

if '##' in S[A:C+1] or '##' in S[B:D+1]:
    print('No')  # そもそも移動経路の中に岩が二つ並んでいたら不可能ということ！
else:
    if C < D:  # この状態ならBにいる人をDに動かしてから、AをCに動かすだけでOK
        print('Yes')
    elif C > D:  # Aの目的地が、Bの目的地よりも右にあるなら
        # B-1からD+2にまでの中にBくんを退避させることが可能なスペースがあるか。
        # BくんはDまでしか動けない
        if "..." in S[B-1:D+2]:
            print('Yes')
        else:
            print('No')


Measured memory_bytes: 3572
import java.util.Scanner;

public class Main{

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int w = sc.nextInt();
        int pos_a = sc.nextInt();
        int pos_b = sc.nextInt();

        int ans;
        int x = pos_b - (pos_a + w);
        int y = pos_a - (pos_b + w);

        if (x > 0) {
            ans = x;
        } else if (y > 0) {
            ans = y;
        } else {
            ans = 0;
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 21716
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <functional>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cassert>
#define InfL 2000000000
#define InfLL 4000000000000000000LL
#define mod 1000000007
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=(n-1);i>=0;i--)
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<db> vd;

int main() {
	ll N;
	string X;
	cin >> N;
	cin >> X;
	ll popcount = 0;
	rep(i, N)
		popcount += (int)(X[i] == '1');
	vl modlist(3);
	modlist[0] = popcount - 1;
	modlist[1] = popcount;
	modlist[2] = popcount + 1;
	vector<vl> mod2(3);
	vl mod2_prev(3);
	rep(i, 3) {
		if (modlist[i] <= 0)
			continue;
		mod2[i].resize(N + 1);
		mod2[i][0] = 1 % modlist[i];
		rep(j, N) {
			mod2[i][j + 1] = mod2[i][j] * 2;
			mod2[i][j + 1] %= modlist[i];
		}
		rep(j, N) {
			if (X[j] == '1') {
				mod2_prev[i] += mod2[i][N - 1 - j];
				mod2_prev[i] %= modlist[i];
			}
		}

	}
	rep(i, N) {
		ll ans = 0;
		ll nxt = 0;
		ll diff = 0;
		ll popcount_new = popcount;
		if (X[i] == '1') {
			popcount_new--;
			if (popcount_new > 0) {
				nxt = mod2_prev[0];
				nxt -= mod2[0][N - 1 - i];
				nxt += modlist[0];
				nxt %= modlist[0];
				ans = 1;
			}
		}
		if (X[i] == '0') {
			popcount_new++;
			if (popcount_new > 0) {
				nxt = mod2_prev[2];
				nxt += mod2[2][N - 1 - i];
				nxt %= modlist[2];
				ans = 1;
			}
		}
		while (nxt != 0) {
			ans++;
			ll modtmp = 0;
			rep(b, 40)
				modtmp += (nxt >> b) % 2;
			nxt %= modtmp;
		}
		cout << ans << "\n";
	}
	return 0;
}

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

int main()
{
	int a,b;
	int sum = 0;

	cin >> a;
	cin >> b;

	if( a > b ){
		sum += a;
		a--;
	} else {
		sum += b;
		b--;
	}

	if( a > b ){
		sum += a;
		a--;
	} else {
		sum += b;
		b--;
	}

	cout << sum << endl;

	return 0;
}

Measured memory_bytes: 256
i=1
N=int(input())
while i<=N:
    x,y,z=map(int,input().split())
    if x**2+y**2==z**2:
        print('YES')
        i+=1
    elif y**2+z**2==x**2:
        print('YES')
        i+=1
    elif x**2+z**2==y**2:
        print('YES')
        i+=1
    else:
        print('NO')
        i+=1


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

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

const int INF = 1e9;
const int MOD = 1e9 + 7;

// 4近傍、8近傍
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

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

  if (s.size() <= k) {
    cout << s << endl;
  } else {
    cout << s.substr(0, k) << "..." << endl;
  }

  return 0;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
template <class T> inline bool chmin(T &a, T b) {if (a > b){a = b;return true;}return false;}
template <class T> inline bool chmax(T &a, T b) {if (a < b){a = b;return true;}return false;}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m; cin>>n>>m;
    int p[100010];
    int y[100010];
    vector<vector<int>> c(100010);
    rep(i, m) {
        cin>>p[i]>>y[i];
        c[p[i]].push_back(y[i]);
    }
    rep(i, n){
        sort(c[i+1].begin(), c[i+1].end());
    }
    rep(i,m){
        ll idx = lower_bound(c[p[i]].begin(), c[p[i]].end(), y[i])-c[p[i]].begin()+1;
        // printf("%012lld\n", ll(1000000*p[i]) + idx);
        printf("%06d", p[i]);
        printf("%06d\n", idx);
    }
}


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

int main() {
	int m[200], f[200], r[200];
	int x, y, z, i = 0;

	while(1){
		cin >> x >> y >> z;
		if (x == -1 && y == -1 && z == -1) break;
		else {
			m[i] = x;
			f[i] = y;
			r[i] = z;
		}
		i++;
	}

	for (int j = 0; j < i; j++) {
		if (m[j] == -1 || f[j] == -1) cout << "F" << endl;
		else if (m[j] + f[j] >= 80) cout << "A" << endl;
		else if (m[j] + f[j] < 80 && m[j] + f[j] >= 65) cout << "B" << endl;
		else if (m[j] + f[j] < 65 && m[j] + f[j] >= 50) cout << "C" << endl;
		else if (m[j] + f[j] < 50 && m[j] + f[j] >= 30) {
			if (r[j] >= 50) cout << "C" << endl;
			else cout << "D" << endl;
		}
		else if (m[j] + f[j] < 30) cout << "F" << endl;
	}
	return 0;
}

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

typedef long long ll;
typedef vector<long long> vll;
typedef vector<int> vi;
typedef pair<int, int> pi;

#define pb push_back
#define rep(i, l, n) for (int i = (l); i < n; i++)
#define rep_cs(i, l, n) for (int i = (l); i <= n; i++)
#define rep_d(j, n) for (int j = n; j >= 0; j--)
#define rep_d_op(j, n, a) for (int j = n; j >= a; j--)

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 int MOD = 1000000007;
const vector<int> dx = {1, 0};
const vector<int> dy = {0, 1};
const ll INF = 1LL << 60;

// int max = *std::max_element(vec.begin(), vec.end());
// int sum = accumulate(list, list + size, 0);

int GCD(int a, int b) { return b ? GCD(b, a % b) : a; }

using Graph = vector<vector<int>>;
Graph G;
vector<bool> seen;
void dfs(const Graph &G, int v)
{
    seen[v] = true;

    for (auto next_v : G[v])
    {
        if (seen[next_v])
            continue;
        dfs(G, next_v);
    }
}

int main()
{
    int x;
    cin >> x;
    int dp[101000] = {0};
    int a[6] = {100,
                101,
                102,
                103,
                104,
                105};

    dp[0] = 1;

    rep(i, 0, 6)
    {
        rep(j, 0, x)
        {
            if (dp[j] == 1)
            {
                dp[j + a[i]] = 1;
            }
        }
    }

    cout << dp[x] << endl;
}

Measured memory_bytes: 640
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<complex>
#include<cstdio>
#define initdp(a,b) for(int i=0;i<=a;i++)for(int j=0;j<=b;j++)dp[i][j]=-1;
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define ppi pair<pii,int>
#define pip pair<int,pii>
#define ll long long
#define pll pair<ll,ll>
#define rep(i,n) for(int i=0;i<n;i++)
#define repd(i,n) for(int i=n-1;i>=0;i--)
#define inf 1000000001
#define inf1 1000000000000000001
#define mod 1000000007
#define pie 3.14159265358979323846
#define N 1000005
#define mid(l,r) l+(r-l)/2
using namespace std;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int ddx[8]={1,1,0,-1,-1,-1,0,1},ddy[8]={0,1,1,1,0,-1,-1,-1};
void mad(ll &a,ll b){a=(a+b)%mod;if(a<0)a+=mod;}
ll gcd(ll a,ll b){ if(!a)return b;return gcd(b%a,a);}

void solve(){
	int s;
	cin>>s;
	int n=s+5;
	ll int a[s];
	for(int i=0;i+3<=s;i++)a[i]=3+i;
	ll dp[s+1];
	memset(dp,0,sizeof(dp));
	dp[0]=1;
	for(int i=0;i<s;i++){
		for(int j=0;j+3<=s;j++){
			if(i+a[j]<=s)dp[i+a[j]]=(dp[i+a[j]]+dp[i])%mod;
		}
	}
	cout<<dp[s];
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t;
	//cin>>t;
	t=1;
	while(t--){
		solve();
	}
}

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

#define rep(i,n) for(int i = 0; i < (n); i++)
#define ll long long

using namespace std;

int main(){
  int result=0;
  int a=-1,z;
  string s;cin>>s;

  rep(i,s.size()){
    if(s[i]=='A' && a==-1)a=i;

    if(s[i]=='Z')z=i;
  }
  cout<<z-a+1;
  return 0;
}

Measured memory_bytes: 640
#include <stdint.h>
#include <stdio.h>
#include <algorithm>

/* At most four digits. */
unsigned readUnsigned() {
    int c;
    do { c = ::getchar_unlocked(); } while (c < '0');
    unsigned result = c - '0';
    if ((c = ::getchar_unlocked()) >= '0') {
        result *= 10;
        result += c - '0';
        if ((c = ::getchar_unlocked()) >= '0') {
            result *= 10;
            result += c - '0';
            if ((c = ::getchar_unlocked()) >= '0') {
                result *= 10;
                result += c - '0';
            }
        }
    }
    return result;
}

unsigned N;
unsigned A[2048];

unsigned bitDP() {
    unsigned sum = 0;
    for (unsigned i = 0; i < N; ++i) {
        sum += A[i];
    }

    unsigned optimal = (sum + 1) / 2;
    unsigned maxMedian = optimal + A[N-1];

#define DP(i) ((dp[(i)/64] >> ((i)%64)) & 1)

    unsigned maxDp = 0;
    uint64_t dp[(1024 * 2048 + 63) / 64] = {0};
    dp[0] |= 1;
    for (unsigned i = 0; i < N; ++i) {
        unsigned x = A[i];
        unsigned step = x / 64;
        unsigned offset = x % 64;
        unsigned start = (std::min(maxDp, maxMedian - x) + 63) / 64;
        for (unsigned j = start + 1; j--;) {
            if (offset != 0) {
                dp[j + step + 1] |= dp[j] >> (64 - offset);
            }
            dp[j + step] |= dp[j] << offset;
        }
        maxDp += x;
        if (DP(optimal)) {
            break;
        }
    }

    for (unsigned d = 0;; ++d) {
        if (DP(optimal + d)) {
            return optimal +  d;
        }
        if (DP(optimal - d)) {
            return optimal - d;
        }
    }
}

unsigned simpleDP() {
    unsigned sum = 0;
    for (unsigned i = 0; i < N; ++i) {
        sum += A[i];
    }

    unsigned optimal = (sum + 1) / 2;
    unsigned maxMedian = optimal + A[N-1];

    unsigned maxDp = 0;
    uint8_t dp[1024 * 2048] = {0};
    dp[0] = 1;
    for (unsigned i = 0; i < N; ++i) {
        unsigned x = A[i];
        unsigned start = std::min(maxDp, maxMedian - x);
        for (unsigned j = start + 1; j--;) {
            dp[j + x] |= dp[j];
        }
        maxDp += x;
        if (dp[optimal]) {
            break;
        }
    }

    for (unsigned d = 0;; ++d) {
        if (dp[optimal + d]) {
            return optimal +  d;
        }
        if (dp[optimal - d]) {
            return optimal - d;
        }
    }
}

int main() {
    N = readUnsigned();
    for (unsigned i = 0; i < N; ++i) {
        A[i] = readUnsigned();
    }
    
    std::sort(&A[0], &A[N]);

    //printf("%u\n", simpleDP());
    printf("%u\n", bitDP());
}


Measured memory_bytes: 384
#include "bits/stdc++.h"
#define ll long long
#define PI 3.1415926535897932384626433832795l
#define MAX_NUM 1000000000
#define line printf("-----------------\n");
using namespace std;
int SET(int N, int pos) { return N = N | (1 << pos); }
int RESET(int N, int pos) { return N = N & ~(1 << pos); }
bool CHECK(int N, int pos) { return (bool)(N & (1 << pos)); }
template <typename T>
inline T __lcm(T a, T b)
{
    return (a * b) / __gcd(a, b);
}
struct node
{
    ll x, y, cnt;
};
int dx[] = {0, 1, 0, -1, -1, 1, -1, 1};
int dy[] = {1, 0, -1, 0, 1, 1, -1, -1};


void solve()
{
    ll a,b;
    cin>>a>>b;
    cout<<a*b<<endl;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("inputf.txt", "r", stdin);
    freopen("outputf.txt", "w", stdout);
#endif // ONLINE_JUDGE
    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL);
    //cout.tie(NULL);

    solve();
    return 0;
}

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

public class Hello
{
    public static void Main()
    {
        var line1 = Console.ReadLine().Split(' ');
        var h = int.Parse(line1[0]);
        var w = int.Parse(line1[1]);

        if (h == 1 && w == 1)
        {
            Console.WriteLine(0);
            return;
        }

        var map = new int[h, w];
        for (int i = 0; i < h; ++i)
            for (int j = 0; j < w; ++j)
                map[i, j] = int.MaxValue;

        var black = new List<KeyValuePair<int, int>>();

        for (int i = 0; i < h; ++i)
        {
            var line = Console.ReadLine();
            for (int j = 0; j < w; ++j)
            {
                if (line[j] == '#')
                    black.Add(new KeyValuePair<int, int>(i, j));
            }
        }

        var next = new List<KeyValuePair<int, int>>();

        int step = -1;

        while (black.Count > 0)
        {
            ++step;
            next.Clear();

            foreach (var p in black)
            {
                var i = p.Key;
                var j = p.Value;

                if (step < map[i, j])
                {
                    map[i, j] = step;
                    if (i > 0)
                        next.Add(new KeyValuePair<int, int>(i - 1, j));
                    if (i < h - 1)
                        next.Add(new KeyValuePair<int, int>(i + 1, j));
                    if (j > 0)
                        next.Add(new KeyValuePair<int, int>(i, j - 1));
                    if (j < w - 1)
                        next.Add(new KeyValuePair<int, int>(i, j + 1));
                }
            }

            var tmp = black;
            black = next;
            next = tmp;
        }

        Console.WriteLine(step - 1);
    }
}


Measured memory_bytes: 72300
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define reps(i,a,b) for(int i=a;i<b;++i)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
template<typename T> inline bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T> inline bool chmin(T &a,T b){if(b<a){a=b;return 1;}return 0;}
template<typename T> vector<T> make_vec(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_vec(size_t a,Ts... ts){return vector<decltype(make_vec<T>(ts...))>(a,make_vec<T>(ts...));}
template<typename T,typename U,typename... V>
typename enable_if<is_same<T,U>::value>::type fill_v(U &u,const V... v){u=U(v...);}
template<typename T,typename U,typename... V>
typename enable_if<!is_same<T,U>::value>::type fill_v(U &u,const V... v){for(auto &e:u)fill_v<T>(e,v...);}

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

    string s;
    while (cin >> s, s != "0") {
        int sum = 0;
        size_t n = s.size();
        for (size_t i = 0; i < n; ++i) {
            sum += s[i] - '0';
        }
        cout << sum << endl;
    }
}



Measured memory_bytes: 3184
#include<iostream>
#include<cstdio>

int main(){
  int a,b,c;
  int Rec=0,Dia=0;

  while(std::scanf(" %d,%d,%d",&a,&b,&c)+1){
    if(a*a+b*b==c*c){
      Rec++;
    }
    if(a==b){
      Dia++;
    }
  }
  std::cout << Rec << std::endl;
  std::cout << Dia << std::endl;
}

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

// 1 つの証言を表す構造体
using pint = pair<int, int>;  // 「人」と「0 or 1」

// 入力
int N;
vector<vector<pint>> v;

// 整数 bit に対応する「決め打ち」が整合しているかを判定
bool judge(int bit) {
  // i 人目の証言を検証する
  for(int i = 0; i < N; ++i) {
    // i 人目が「不親切」だったら、証言はすべて無意味
    if(!(bit & (1 << i))) continue;

    // それぞれ確認
    for(pint xy : v[i]) {
      int x = xy.first;   // x が
      int y = xy.second;  // y = 1: 正直、y = 0: 不親切

      // y = 1 なのに「不親切」だったらダメ
      if(y == 1 && !(bit & (1 << x))) return false;

      // y = 0 なのに「正直者」だったらダメ
      if(y == 0 && (bit & (1 << x))) return false;
    }
  }
  return true;
}

int main() {
  cin >> N;
  v.resize(N);
  for(int i = 0; i < N; ++i) {
    int A;
    cin >> A;
    v[i].resize(A);
    for(int j = 0; j < A; ++j) {
      cin >> v[i][j].first >> v[i][j].second;
      --v[i][j].first;  // 0-indexed に
    }
  }

  int res = 0;
  for(int bit = 0; bit < (1 << N); ++bit) {
    // 矛盾 check
    if(judge(bit)) {
      // bit に含まれる人数を数える
      int count = 0;
      for(int i = 0; i < N; ++i) {
        if(bit & (1 << i)) ++count;
      }
      res = max(res, count);
    }
  }

  cout << res << endl;
}


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

#define N 101

void push(int x);
void pop(void);
int isEmpty(void);
int isFull(void);
void visit(int);
void dfs(int);
int next(int, int);

int d[N], f[N], A[N][N], t = 0, top = 0, n, S[N];
char color[N];

int main(){
  int i, j, k, l, m;
  
  scanf("%d",&n);
  for(i = 1; i <= n; i++){
    d[i] = 0;
    f[i] = 0;
    for(j = 1; j <= n; j++){
      A[i][j] = 0;
    }
  }
  for(i = 1; i <= n; i++){
    scanf("%d%d", &l, &m);
    for(j = 1; j <= m; j++){
      scanf("%d", &k);
      A[l][k] = 1; 
    }
  }

  dfs(n);

  for(i = 1; i <= n; i++){
    printf("%d %d %d\n", i, d[i], f[i]);
  }

  return 0;
}

void dfs(int u){
  int i; 

  for(i = 1; i <= u; i++){
    color[i] = 'w';
  }
  t = 0;

  for(i = 1; i <= u; i++){
    if(color[i] == 'w') visit(i);
  }

}

void visit(int r){
  int u, v;

  push(r);
  color[r] =  'g';
  d[r] = ++t;
  while(isEmpty() != 0){
    u = S[top];
    //printf("%d\n",top);
    v = next(u, n);
    if(v != NULL){
      if(color[v] == 'w'){
	push(v);
	color[v] = 'g';
	d[v] = ++t;
      }
      else{
	pop();
	color[u] = 'b';
	f[u] = ++t;
      }
    }
  }

}

int next(int u, int n){
  int i;

  for(i = 1; i <= n; i++){
    if((A[u][i] == 1) && (d[i] == 0)) return i;
  }

  return -1;

}

void push(int x){
  if(isFull() == 0){
    fprintf(stderr, "overfullow");
    exit(8);
  }
  top++;
  S[top] = x;
}

void pop(void){
  if(isEmpty() == 0){
    fprintf(stderr, "underfullow");
    exit(8);
  }
  top--;
}

int isEmpty(void){
  if(top  == 0) return 0; 
  else return 1;
}

int isFull(void){
  if(top >= N -1) return 0; 
  else return 1;
}

Measured memory_bytes: 636
#include <bits/stdc++.h>
using namespace std; 
const int maxn=200010;
int a[maxn] , b[maxn];
int main()
{
	int n;
	while (~scanf ("%d",&n)){
		for (int i=0; i<n; i++)  scanf ("%d",&a[i]);
		
		int m;
		scanf ("%d",&m);
		for (int i=0; i<m; i++)  scanf ("%d",&b[i]);
		
		sort(a,a+n);
		sort(b,b+m);
		bool flag = true;
		int i=0 , j=0;
		while (i<n && j<m){
			if (a[i] == b[j]){
				i ++;
				j ++;
			}
			else if (a[i] < b[j])  i ++;
			else{
				flag = false;
				break;
			}
		}
		if (flag)  puts("YES");
		else  puts("NO");
	}
	return 0;
}

Measured memory_bytes: 1792
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=100000;
int n;
int cnt[MAXN+10];
int main()
{
	scanf("%d",&n);
	for(int i=1,a;i<=n;++i)
	{
		scanf("%d",&a);
		++cnt[a];
	}
	int res=0;
	for(int i=1;i<=MAXN;++i)res=max(res,cnt[i]+cnt[i-1]+cnt[i+1]);
	printf("%d",res);
	return 0;
}


Measured memory_bytes: 640
# greedy

N = int(input())
red = [list(map(int, input().split())) for _ in range(N)]
blue = [list(map(int, input().split())) for _ in range(N)]

"""
赤点のx座標 < 青点のx座標 and 赤点のy座標 < 青点のy座標
その中で赤点のy座標は最大のものを選ぶ
"""

sort_red = sorted(red, key=lambda x:x[1], reverse=True) # y座標で降順ソート
sort_blue = sorted(blue, key=lambda x:x[0]) # x座標で昇順ソート

ans = 0
for i in range(N):
  for j in range(len(sort_blue)):
    if (sort_red[i][0] < sort_blue[j][0] and 
        sort_red[i][1] < sort_blue[j][1]):
      ans += 1
      del sort_blue[j]
      break
print(ans)        

Measured memory_bytes: 3064
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <math.h>
#include <algorithm>

using namespace std;
int main()
{
  int N;
  cin >> N;
  cout << (N-2) * 180 << endl;

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<cstdio>
#include<cmath>
#include<utility>
#include<algorithm>
#include<bitset>
using namespace std;
int n,ans;
char W;
int main(){
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>W;
    if(W=='Y')ans=1;
  }
  if(ans==1)cout<<"Four"<<endl;
  else cout<<"Three"<<endl;
  return 0;
}



Measured memory_bytes: 256