akhauriyash/Code-Regression huggingface dataset:
{-# LANGUAGE OverloadedStrings #-}
import qualified Data.ByteString.Char8 as B
import qualified Data.Maybe as Maybe
import qualified Data.Char as Char
import Control.Monad (replicateM)
import Data.List (sortOn)
import Data.Ord (Down(..))
import Data.Int (Int64)

main :: IO ()
main =
    print =<< runParser solve <$> B.getContents

solve :: Parser Int64
solve = do
    nEatRed     <- parseInt
    nEatGreen   <- parseInt
    nRed        <- parseInt
    nGreen      <- parseInt
    nWhite      <- parseInt
    redApples   <- replicateM nRed   (fromIntegral <$> parseInt)
    greenApples <- replicateM nGreen (fromIntegral <$> parseInt)
    whiteApples <- replicateM nWhite (fromIntegral <$> parseInt)
    let
        apples = concat
            [ take nEatRed   (sortOn Down redApples)
            , take nEatGreen (sortOn Down greenApples)
            , whiteApples
            ]
        bestApples = take (nEatRed + nEatGreen) (sortOn Down apples)
    return $ sum bestApples

-------------------------------------------------------------------------------

newtype Parser a =
    Parser (B.ByteString -> (a, B.ByteString))

instance Functor Parser where
    fmap f (Parser parser) =
        Parser $ \input ->
            let (v, remainder) = parser input in
                (f v, remainder)

instance Applicative Parser where
    pure v =
        Parser $ \input ->
            (v, input)

    (Parser parser1) <*> (Parser parser2) =
        Parser $ \input ->
            let
                (f, remainder1) = parser1 input
                (v, remainder2) = parser2 remainder1
            in
                (f v, remainder2)

instance Monad Parser where
    return = pure

    (Parser parser1) >>= f =
        Parser $ \input ->
            let
                (v, remainder) = parser1 input
                Parser parser2 = f v
            in
                parser2 remainder

consumeSpace :: Parser ()
consumeSpace =
    Parser $ \input ->
        ((), B.dropWhile Char.isSpace input)

parseInt_ :: Parser Int
parseInt_ =
    Parser $ \input ->
        Maybe.fromJust (B.readInt input)

parseInt :: Parser Int
parseInt =
    consumeSpace *> parseInt_

runParser :: Parser a -> B.ByteString -> a
runParser (Parser parser) input =
    fst $ parser input

-------------------------------------------------------------------------------


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

class Data{
public:
  int correct;
  int submit[10];
  int time;
  int team;
  Data():correct(0),time(0),team(0){
    for(int i=0;i<10;i++)
      submit[i]=0;
  }
};

bool operator>(const Data &d1,const Data &d2){
  if(d1.correct!=d2.correct) return d1.correct>d2.correct;
  else if(d1.time!=d2.time) return d1.time<d2.time;
  else return d1.team>d2.team;
}

bool operator==(const Data &d1,const Data &d2){
  return d1.correct==d2.correct && d1.time==d2.time;
}

int main(){
  int m,t,p,r;
  while(cin>>m>>t>>p>>r,m){
    vector<Data> vec(t);
    for(int i=0;i<t;i++)
      vec[i].team=i+1;
    for(int i=0;i<r;i++){
      int a,b,c,d;
      cin>>a>>b>>c>>d;
      b--;
      c--;
      if(d==0){
	vec[b].time+=vec[b].submit[c]*20+a;
	vec[b].correct++;
      }else{
	vec[b].submit[c]++;
      }
    }
    sort(vec.begin(),vec.end(),greater<Data>());
    for(int i=0;i<t-1;i++){
      cout<<vec[i].team;
      if(vec[i]==vec[i+1]){
	cout<<"=";
      }else{
	cout<<",";
      }
    }
    cout<<vec[t-1].team<<endl;
  }
  return 0;
}

Measured memory_bytes: 1200
#include <bits/stdc++.h>
 
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef tuple<ll, ll, ll> ti;
 
#define REP(a,b,c) for(ll a=b;a<(c);a++)
#define PER(a,b,c) for(ll a=b;a>=(c);a--)
 
ll ii(){ ll x; cin >> x; return x; }
string is(){ string x; cin >> x; return x; }
ld id(){ ld x; cin >> x; return x; }
void oi(ll x){ cout << x; }
void od(ld x){ cout << fixed << setprecision(10) << x; }
void os(string x){ cout << x; }
void oe(){ cout << endl; }
void oie(ll x){ oi(x); oe(); }
void ode(ld x){ od(x); oe(); }
void ose(string x){ os(x); oe(); }

ll mod=1000000007;

int main(){
    string S=is();
    string T=is();
    ll ret = 0;
    REP(i,0,S.length()){
        if(S[i]!=T[i]) ret++;
    }
    oie(ret);
    return 0;
}

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

int main() {
  int n,i;
  cin>>n;
  int a[n],h[n-1],ans=0;
  for(i=0;i<n;i++)
    cin>>a[i];
  sort(a,a+n);
  for(i=0;i<n-1;i++){
    h[i]=a[i+1]-a[i];
    ans+=h[i];
  }
  cout<<ans;
  
}

Measured memory_bytes: 256
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    s = str(input().rstrip('\n'))
    mt = 0
    for i in range(n):
        zs = s[i:]
        zln = len(zs)
        zl = [0] * zln
        zi = 1
        zj = 0
        while zi < zln:
            while zi + zj < zln and zs[zj] == zs[zi+zj]:
                zj += 1
            zl[zi] = zj
            if zj == 0:
                zi += 1
                continue
            zk = 1
            while zi + zk < zln and zk + zl[zk] < zj:
                zl[zi+zk] = zl[zk]
                zk += 1
            zi += zk
            zj -= zk
        for j, v in enumerate(zl):
            if v < j + 1:
                mt = max(mt, v)
    print(mt)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 48860
#include <bits/stdc++.h>
using namespace std;
#define rep(i,cc,n) for(int i=cc;i<n;++i)
#define sqrep(i,cc,n) for(long long i=cc;i*i<=n;++i)
#define lrep(i,cc,n) for(long long i=cc;i<n;++i)
#define rrep(i,cc,n) for(long i=cc;i>n;--i)
#define pii pair<int, int>
#define pll pair<long long, long long>
 
using ll = long long;
const ll inf = 1001001001;
const ll inf2 = 1000000000000000000;
const ll mod = 1000000007;


int main() {
   int n;
   cin >> n;
   vector<ll>a(n);
   vector<ll>a2(n);
   rep(i, 0, n){
      cin >> a2[i];
      a[a2[i]-1]++;
   }
   ll sum = 0;
   rep(i, 0, n){
      sum += a[i]*(a[i]-1)/2;
   }
   rep(i, 0, n){
      ll tempsum = sum - a[a2[i]-1]*(a[a2[i]-1]-1)/2;
      tempsum +=  (a[a2[i]-1]-1)*(a[a2[i]-1]-2)/2;
      cout << tempsum << endl;
   }
}

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

using namespace std;
  
int main() {
    int d, n;
    
    cin >> d >> n;
    
    int ret;
    if (d == 0) {
        ret = 1;
    } else if (d == 1) {
        ret = 100;
    } else {
        ret = 10000;
    }
    
    if (n == 100) {
        cout << 101 * ret<< endl; 
    } else {
        cout << n * ret << endl;
    }
}

Measured memory_bytes: 256
#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(){
	
	int n,l;
	cin >> n >> l;
	
	
	int eaten = INF;
	int sum = 0;
	rep(i,n){
		if(abs(eaten) > abs(l+i) )eaten = l+i;
		sum += l+i;
	}
	
	cout << sum-eaten << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n)  for (int i = 0; i < (int) (n); i++)
#define REP1(i, n) for (int i = 1; i <= (int) (n); i++)
#define all(x)     (x).begin(), (x).end()
#define SZ(x)      ((int) (x).size())
using ll = long long;

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


Measured memory_bytes: 256
import Control.Monad
import Data.List

{-
2 2
2 0
0 0
-1 0
1 0
-}

main :: IO ()
main = do
  [n, m] <- getInts
  as <- replicateM n getPairInt
  bs <- replicateM m getPairInt
  mapM_ print $ solve as $ zip [1..] bs

getInts :: IO [Int]
getInts = map read . words <$> getLine

getPairInt :: IO (Int, Int)
getPairInt = do
  [a, b] <- getInts
  return (a, b)

solve :: [(Int, Int)] -> [(Int, (Int, Int))] -> [Int]
solve [] _ = []
solve (s:ss) ts = (getMin s) : solve ss ts
  where
    getMin :: (Int, Int) -> Int
    getMin student = (fst . head) $ sortBy (\a b ->
                      compare (snd a) (snd b))$ map (calcDist student) ts
    calcDist (ax, ay) (idNum, (bx, by)) =
      (idNum, (abs (ax - bx)) + (abs (ay - by)))


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

vector<int> a(100010, 0);
vector<int> s(100010, 0);

int main () {
  int n;
  cin >> n;
  vector<int> d(n);
  for (int i = 0; i < n; i++) {
    cin >> d[i];
    a[d[i]]++;
  }
  for (int i = 1; i < a.size(); i++) {
    s[i] = s[i - 1] + a[i];
  }
  int ans = 0;
  for (int i = 0; i < a.size(); i++) {
    if (s[i] == n - s[i]) {
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1408
n = int(input())
xls = [list(map(int, input().split()))for i in range(n)]
xls.sort(key=lambda x:sum(x))

ans = 0
now = -1e11
for i in range(n):
    if now<=xls[i][0]-xls[i][1]:
        ans += 1
        now = xls[i][0]+xls[i][1]
print(ans)

Measured memory_bytes: 32296
#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
using namespace std;
int main(){
   int a;
   int b;
   cin >> a;
   cin >> b;
   if(a*b%2 == 0){
       cout << "Even" << endl;
   }else{
       cout << "Odd" << endl;
   }
      
   
}

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

int n, m, v, u, ans, lastend;
vector <pair <int, int> > e;
int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++){
		cin >> v >> u;
		e.push_back({u, v}); // start ---> second      end ---> first
	}
	sort(e.begin(), e.end());
	lastend = 0;
	for (int i = 0; i < m; i++){
		if(e[i].second < lastend)
			continue;
		lastend = e[i].first;
		ans++;
	}
	cout << ans << endl;
	return 0;
}

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

int main(){
	
	int a;
	int b;
	int c;
	int tmp;
	
	cin >> a;
	cin >> b;
	cin >> c;
	
	if(a > b){
		tmp = a;
		a = b;
		b = tmp;
	}
	
	if(b > c){
		tmp = b;
		b = c;
		c = tmp;
	}
	if(a > b){
		tmp = a;
		a = b;
		b = tmp;
	}

	cout << a << " " << b << " " << c <<endl;
	
}

Measured memory_bytes: 3088
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)
#define all(x) x.begin(),x.end()

int main(){
  int N;
  cin >> N;
  for(int i = 0;i <= N;i+=4){
    for(int j = 0;i + j <= N;j+=7){
      if(i + j == N){
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  cout << "No" << endl;
}


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

const int MAXN = 2000;
typedef bitset<MAXN> bs;

int N, M;
vector<int> Tadj[MAXN];
bs Gadj[MAXN];
bs onPath[MAXN][MAXN];

void dfs(int root, int cur, int prv = -1) {
	onPath[root][cur][cur] = true;
	for (size_t i = 0; i < Tadj[cur].size(); i++) {
		int nxt = Tadj[cur][i];
		if (nxt == prv) continue;
		onPath[root][nxt] = onPath[root][cur];
	}
	for (size_t i = 0; i < Tadj[cur].size(); i++) {
		int nxt = Tadj[cur][i];
		if (nxt == prv) continue;
		dfs(root, nxt, cur);
		onPath[root][cur] |= onPath[root][nxt];
	}
}

int main() {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N-1; i++) {
		int a, b; scanf("%d %d", &a, &b); a--, b--;
		Tadj[a].push_back(b);
		Tadj[b].push_back(a);
	}
	vector< pair<int, int> > edges;
	for (int i = 0; i < M; i++) {
		int a, b; scanf("%d %d", &a, &b); a--, b--;
		Gadj[a][b] = Gadj[b][a] = true;
		edges.push_back(make_pair(a, b));
	}

	for (int i = 0; i < N; i++) {
		dfs(i, i);
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			onPath[i][j] |= onPath[j][i];
		}
	}
	for (int i = 0; i < N; i++) {
		Gadj[i][i] = true;
	}

	for (size_t i = 0; i < edges.size(); i++) {
		int a = edges[i].first;
		int b = edges[i].second;
		bs cnds = onPath[a][b] & (Gadj[a] ^ Gadj[b]);
		for (int c = cnds._Find_first(); c < int(cnds.size()); c = cnds._Find_next(c)) {
			assert(Gadj[a][c] + Gadj[b][c] == 1);
			if (Gadj[a][c] == false) {
				Gadj[a][c] = Gadj[c][a] = true;
				edges.push_back(make_pair(a, c));
			} else {
				Gadj[b][c] = Gadj[c][b] = true;
				edges.push_back(make_pair(b, c));
			}
		}
	}
	printf("%d\n", int(edges.size()));

	return 0;
}


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


int main(){
    string  S;int Q;
    cin>>S>>Q;
    string  front ,back;
    bool upSideDown;//反転しているか否か
    for(int i=0;i<Q;i++){
        int r=0;
        cin >> r;
        r--;
        if(!r){
            upSideDown=(!upSideDown);
        }else{
            int F;char a;
            cin >> F >> a;
            F--;
            if(!F){
                if(upSideDown){
                    back=back+a;
                }else{
                    front=front+a;
                }
            }else{
                if(!upSideDown){
                    back=back+a;
                }else{
                    front=front+a;
                }
            }
        }
    }
    if(upSideDown){
        reverse(back.begin(),back.end());
        reverse(S.begin(),S.end());
        cout << back + S +front;
    }else{
        reverse(front.begin(),front.end());
        cout << front +S +back;
    }
    return 0;
}

Measured memory_bytes: 1620
N,K = map(int,input().split())
x = list(map(int,input().split()))
result = 1e10
for i in range(N-K+1):
  result = min(result, abs(x[i])+x[i+K-1]-x[i])
  result = min(result, abs(x[i+K-1])+x[i+K-1]-x[i])
print(result)

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

class C{
    public:
        int x, y, cost, hp;
        C(int xx, int yy, int c, int h);
};

C::C(int xx, int yy, int c, int h){
    x = xx;
    y = yy;
    cost = c;
    hp = h;
}

const int HW = 9;
#define FOR(i, j) for (int (i) = 0; (i) < (j); ++(i))

int main(){
    int w, h;
    while(cin >>w >>h){
        if(w == 0 && h == 0) break;
        queue<C> qu;
        int gx, gy;
        bool endflg = false;

        int m[HW][HW];
        //bool gom[HW][HW] = {false};
        FOR(i, HW){
            FOR(j, HW){
                m[i][j] = 0;
            }
        }

        FOR(i, h){
            FOR(j, w){
                cin >>m[i][j];
                if(m[i][j] == 2){
                    C cls(j, i, 0, 6);
                    qu.push(cls);
                }
                if(m[i][j] == 3){
                    gx = j;
                    gy = i;
                }
            }
        }

        int mx[] = {1, -1, 0, 0};
        int my[] = {0, 0, 1, -1};

        while(!qu.empty()){
            C now = qu.front(); qu.pop();

            //gom[now.y][now.x] = true;

            if(now.x == gx & now.y == gy){
                cout <<now.cost <<endl;
                endflg = true;
                break;
            }
            if(now.hp == 1){
                continue;
            }
            
            //cout <<now.y <<", " <<now.x <<", " <<now.cost <<", " <<now.hp <<endl;
            FOR(i, 4){
                int nx = now.x + mx[i], ny = now.y + my[i];
                if(/*gom[ny][nx] == true || */nx < 0 || ny < 0 || nx >= w || ny >= h || m[ny][nx] == 0) continue;
                if(m[ny][nx] == 4){
                    m[ny][nx] = 1;
                    C cls2(nx, ny, now.cost + 1, 6);
                    qu.push(cls2);
                } else{
                    C cls2(nx, ny, now.cost + 1, now.hp - 1);
                    qu.push(cls2);
                }
            }
        }
        if(endflg == false){
            cout <<"-1" <<endl;
        }
    }
    return 0;
}

Measured memory_bytes: 1260
#include<iostream>
#include<vector>
#include<cmath>
#include <bits/stdc++.h> 

using namespace std;
int main()
{
  int n;
  int k;
  cin>>n>>k;
  vector<int>h(n+1,0);
  for(int i=1;i<n+1;i++)
  {
    cin>>h[i];
  }
  vector<int>dp(n+1,INT_MAX);
  dp[0]=0;
  dp[1]=0;
  
  for(int i=2;i<n+1;i++)
  {
    for(int j=1;j<=k;j++)
    {
      if(i>j)
      dp[i]=fmin(dp[i-j]+abs(h[i-j]-h[i]),dp[i]);
      
    }
    
    
    
  }
  cout<<dp[n]<<endl;
  
}


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

#define sz(x) (int)(x.size())
#define FOR(x,y,z) for(int x = y; x <= z; x++)
#define int long long

const int N = 1e5 + 2, inf = 1e18;


int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);  

    int n;
    cin >> n;
    int a[n];
    int all = 0;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        all ^= a[i];
    }
    for(int i = 0; i < n; i++){
        cout << (all ^ a[i]) << " \n"[i == n - 1];
    }
}


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

using namespace std;

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

#define int ll


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

	sort(a,a+n);
	reverse(a,a+n);
	
	ll ans = a[0];
	for(int i=0;i<n-2;i++){
		ans += a[(i/2)+1];
	}

	cout << ans << endl;
	


	return 0;
}


Measured memory_bytes: 5196
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <cctype>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <bitset>
#include <complex>
#include <fstream>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T> T RoundOff(T a){ return int(a+.5-(a<0)); }
template<class T, class C> void chmax(T& a, C b){ if(a < b) a = b; }
template<class T, class C> void chmin(T& a, C b){ if(b < a) a = b; }
template<class T, class C> pair<T, C> mp(T a, C b){ return make_pair(a, b); }

int main()
{
	map<string, int> m;
	m.insert(map<string, int>::value_type("A", 0));
	m.insert(map<string, int>::value_type("B", 0));
	m.insert(map<string, int>::value_type("AB", 0));
	m.insert(map<string, int>::value_type("O",0));

	int n;
	char k;
	string t;

	while(cin >> n >> k >> t)
		m[t]++;
	
	cout << m["A"] << endl << m["B"] << endl << m["AB"] << endl << m["O"] << endl;
}

Measured memory_bytes: 0
// Problem URL: https://atcoder.jp/contests/abc177/tasks/abc177_b
#include <bits/stdc++.h>
using namespace std;

int main()
{
  string s, t;
  getline(cin, s);
  getline(cin, t);
  int minimum = t.size();
  for (int i = 0; i < s.size() - t.size() + 1; i++) {
    int minCount = 0;
    for (int j = 0; j < t.size(); j++) {
      if (s[i + j] != t[j]) {
        minCount++;
      }
    }
    minimum = min(minCount, minimum);
  }
  cout << minimum;
  return 0;
}


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

using namespace std;

#define all(v)				((v).begin()), ((v).end())
#define allr(v)				((v).rbegin()), ((v).rend())
#define sz(v)				((int)((v).size()))
#define rep(i, v)		for(int i=0;i<sz(v);++i)
#define lp(i, n)		for(int i=0;i<(int)(n);++i)
#define lpi(i, j, n)	for(int i=(j);i<(int)(n);++i)
#define lpd(i, j, n)	for(int i=(j);i>=(int)(n);--i)
#define ll long long
#define pb					push_back
#define fIO ios_base::sync_with_stdio(0);cin.tie(0);

const ll oo = 1e8;
const double pi = 3.1415926535897;


const double EPS = (1e-7);
int dcmp(double x, double y) {	return fabs(x-y) <= EPS ? 0 : x < y ? -1 : 1;	}


typedef vector<int>                vi;
typedef vector<pair<int,int>>      vii;
typedef vector<ll>                 vll;
typedef vector<double>             vd;
typedef vector< vi >               vvi;
typedef vector< vd >               vvd;
typedef vector<string>             vs;

/**
    * PLEASEEE READDD PROBLEEEM CARFULLY ****
    * Always check for OVERFLOW ll vs int
    * Always check for array bounds
    * Check for function return
    * READ OUTPUT SECTION AGAIN!!!
**/

struct edge{
    int from, to, w;

    edge(){}
    edge(int x, int y, int we): from(x), to(y), w(we){}

    bool operator < (const edge &rhs) const{
        return w > rhs.w;
    }

};

const int W = 100005, N = 6;

int item[] = {100, 101, 102, 103, 104, 105};
int dp[W][N];

int sol(int w, int idx) {
    if(w < 0) return -1e9;
    if(idx == 6) return 0;

    int &ret = dp[w][idx];

    if(ret != -1) return ret;

    ret = sol(w, idx + 1);

    return ret = max(ret, sol(w - item[idx], idx) + item[idx]);
}

int main(){
    fIO

    int x;
    cin >> x;

    memset(dp, -1, sizeof(dp));
    cout << (sol(x, 0) == x) ;

}










Measured memory_bytes: 2688
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
lint inf=1e15;
lint dp[2][5010][5010][2];
vector<int> gr[5010];
lint a[5010];
int n;
int dfs(int v,int u){
	int ch=0,now=0,ne=1;
	if(a[v]<0) dp[0][v][0][1]=a[v];else dp[0][v][0][0]=a[v];
	//cout<<v<<' '<<dp[0][v][0][0]<<' '<<dp[0][v][0][0]<<endl;
	rep(i,gr[v].size()){
		int w=gr[v][i];
		if(w==u) continue;
		rep(j,ch+3) dp[ne][v][j][0]=dp[ne][v][j][1]=inf;
		int c2=dfs(w,v),x=1-gr[w].size()%2;
		rep(j,ch+1) rep(k,c2+1){
			//切る
			if(dp[x][w][k][0]<inf/2 || dp[x][w][k][1]<0){
				//cout<<"hoge"<<endl;
				dp[ne][v][j+k+1][0]=min(dp[ne][v][j+k+1][0],dp[now][v][j][0]);
				dp[ne][v][j+k+1][1]=min(dp[ne][v][j+k+1][1],dp[now][v][j][1]);
			}
			//切らない
			rep(l,2) rep(m,2){
				//cout<<"huga"<<' '<<dp[now][v][j][l]<<' '<<dp[x][w][k][m]<<' '<<x<<w<<k<<m<<endl;
				dp[ne][v][j+k][(l|m)]=min(dp[ne][v][j+k][(l|m)], dp[now][v][j][l]+dp[x][w][k][m]);
			}
		}
		ch+=c2+1;
		rep(j,ch+1){
			//cout<<v<<' '<<j<<' '<<dp[ne][v][j][0]<<' '<<dp[ne][v][j][1]<<endl;
		}
		swap(now,ne);
	}
	return ch;
}
int main()
{
	int x,y,out=5010;
	cin>>n;
	rep(i,n) cin>>a[i];
	rep(i,n-1){
		cin>>x>>y;x--;y--;
		gr[x].pb(y);gr[y].pb(x);
	}
	rep(k,2) rep(i,5005) rep(j,5005) dp[k][i][j][0]=dp[k][i][j][1]=inf;
	dfs(0,-1);
	rep(i,n+1){
		if(dp[gr[0].size()%2][0][i][0]<inf/2 || dp[gr[0].size()%2][0][i][1]<0L) out=min(out,i);
	}
	cout<<out<<endl;
}


Measured memory_bytes: 785280
# -*- coding: utf-8 -*-

#すぬけくんは 3 匹のヤギにクッキーを渡したいです。
#すぬけくんは A 枚のクッキーが入った缶と、B 枚のクッキーが入った缶を持っています。
#すぬけくんは A,B,A+B のいずれかの枚数のクッキーをヤギたちに渡すことができます。
#3 匹のヤギが同じ枚数ずつ食べられるようにクッキーを渡すことが可能かどうか判定してください。
#3 匹のヤギが同じ枚数ずつ食べられるようにクッキーを渡すことが可能ならば Possible と、
#そうでなければ Impossible と出力せよ。

A = input().split()
#A = [3, 3]
x = int(A[0])
y = int(A[1])

if x % 3 ==0:
    print("Possible")

elif y % 3 ==0:
    print("Possible")
    
elif (x + y) % 3 ==0:
    print("Possible")

    
else:
    print("Impossible")
    



Measured memory_bytes: 2940
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <cstdio>
#include <cmath>

using namespace std;

int main(){
    char a[4];
  for(int i=0;i<4;i++){
    cin>>a[i];
  }
  if((a[0]==a[1]&&a[1]==a[2])||(a[1]==a[2]&&a[2]==a[3])){
    cout<<"Yes";
  }else{
    cout<<"No";
  }
    return 0;
}

Measured memory_bytes: 256
/*input
12 21 10
*/

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char const *argv[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int a, b, x;
    cin >> a >> b >> x;

    double xd = (double) x / a;
    int V = a * b;

    double ans; 
    if (xd * 2 < V) {
        ans = 90 - atan2(2 * xd, b * b) * 180 / M_PI;
    } else {
        ans = atan2(2 * (V - xd), a * a) * 180 / M_PI;
    }

    cout.precision(10);
    cout << fixed << ans;

    return 0;
}

Measured memory_bytes: 256
fun main(arg: Array<String>) {
    val N = nextInt()
    val V = listOfDouble().sorted()
    println(V.reduce { acc, value -> (acc + value) / 2.0 })
}
fun next() = readLine()!!
fun nextInt() = Integer.parseInt(next())
fun listOfString() = next().split(" ")
fun listOfDouble() = listOfString().map { java.lang.Double.parseDouble(it) }


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



int main() 
{
     int k, a, b;
    cin >> k >> a >> b;

    bool ans = false;
    for (int i = a; i <= b; i++)
    {
        if(i%k==0)
            ans = true;

    }

    cout << (ans ? "OK" : "NG")<<endl;

    return 0;
}

Measured memory_bytes: 3624
import bisect
N=int(input())
L=list(map(int, input().split()))
#a<b+c
#b<c+a
#c<a+b
#a<=b<=c
#c<a+b
L=sorted(L)
ans=0
for i in range(N-2):
    for j in range(i+1,N-1):
        x=bisect.bisect_left(L,L[i]+L[j])
        ans+=x-(j+1)
print(ans)

Measured memory_bytes: 3188
#include <iostream>
#include <math.h>
#include <algorithm>
#include <functional> 
#include <string>
#include <vector>

#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <utility>

using namespace std;

typedef long long LL;

#define dump(c) { for (auto it = c.begin(); it != c.end(); ++it) if (it == c.begin()) cout << *it; else cout << ' ' << *it; cout << endl; } 


int main()
{

    int N;
    cin >> N;

    int cnt = 1;
    cnt <<= N;

    multiset< int, greater<int> > S; 

    for (int i = 0; i < cnt; ++i) {
        int life;
        cin >> life;
        S.insert(life);
    }

    bool ok = true;
    multiset< int, greater<int> > curr; //! current slimes
    curr.insert(*S.begin());
    S.erase(S.begin());

    for (int i = 0; ok && i < N; ++i) { //! repeat N generations
        vector<int> newKids;
        for (auto p : curr) { //! for each slime in the durrent generation
            auto ik = S.upper_bound(p);
            if (ik == S.end()) {
                ok = false;
                break;
            } else {
                newKids.push_back(*ik);
                S.erase(ik);
            }
        }
        if (ok) {
            for (int k : newKids) {
                curr.insert(k);
            }
        }
    }

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

    return 0;
}


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

const ll INF = 1e18;

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

    ll N;
    cin >> N;

    if (N == 1) {
        cout << 0 << endl;
        exit(0);
    }

    map<ll, ll> mp;
    ll res = N;
    for (ll i = 2; i * i <= N; ++i) {
        while (res % i == 0) {
            res /= i;
            mp[i]++;
        }
    }
    if (res != 1) {
        mp[res]++;
    }

    ll ans = 0;
    for (auto &p : mp) {
        ll x = p.second;
        for (ll i = 1; i <= x; ++i) {
            x -= i;
            ans++;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3600
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<cmath>
#include<climits>
#include<ctime>
#include<cstring>
#include<stack>
#include<queue>
#include<sstream>
#include<string>
#include<set>
#include<array>

#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i);
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())

using namespace std;


int main(){
  
  int K,T;
  cin >> K >> T;
  vector<int> l = vector<int>(T,0);
  
  int max_t=0;
  rep(i,T){
    cin >> l[i];
    max_t = max(l[i],max_t);
  }
  if(T == 1) cout << K -1 << endl;
  else if(K - max_t > max_t) cout << 0 << endl;
  else cout << max_t-(K-max_t+1) << endl;
}




Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(i=a;i<=b;i++)
using namespace std;
typedef long long ll;
const int mod=998244353;
const int lim=18,maxn=(1<<20)+5,N=110;
int F[lim+1][maxn],G[lim+1][maxn];
int dp[10][N];int g[N][N];
int a[N];char s[N];
ll p[N],c[N][N];
int n;

void work(int K){
	int i,j,k;int cur,x;
	rep(i,0,(1<<K)-1){
		rep(j,1,K/2)	if(K%j==0){
			x=i;cur=p[j];rep(k,1,K/j)	cur&=x,x>>=j;		
			G[K][i]=(G[K][i]+F[j][cur])%mod;
		}
		//F[K][i]=(F[K][i]+1ll*F[K-1][i>>1]*((i&1)+1))%mod;
		rep(j,1,K)	if(G[j][i&p[j]])	F[K][i]=(F[K][i]+1ll*G[j][i&p[j]]*F[K-j][i>>j])%mod;
	}
}	

void init(){
	int i;
	rep(i,1,50)	p[i]=(1ll<<i)-1;
	F[0][0]=1;
	G[1][0]=F[1][0]=1;F[1][1]=G[1][1]=2;
	rep(i,2,lim)	work(i);
}

int solve(int K,ll w,int d){
	if(K<=lim)	return F[K][w];
	int i,j,k;ll cur;int x;int opt;
	//memset(dp[d],0,(K+1)*sizeof(int));
	rep(i,0,K)	dp[d][i]=0;
	dp[d][0]=1;
	rep(i,0,K-1) if(dp[d][i]){
		if(K-i<=lim){dp[d][K]=(dp[d][K]+1ll*dp[d][i]*F[K-i][w>>i])%mod;continue;}
		opt=(w>>i)&1;
		dp[d][i+1]=(dp[d][i+1]+1ll*dp[d][i]*(opt+1))%mod;
		rep(j,1,(K-i)>>1){		
			for(cur=(w&p[i+j])>>i,x=i+j,k=2;k<=(K-i)/j;k++){
				cur&=(w&p[x+j])>>x;x+=j;
				dp[d][x]=(dp[d][x]+1ll*dp[d][i]*solve(j,cur,d+1))%mod;
			}
		}
	}
	return dp[d][K];
}

int getG(int l,int r){
	if(r-l+1<=lim)	return G[r-l+1][c[l][r]];
	int len=r-l+1;int ret=0;int i;
	ll cur;int x;
	rep(i,1,len/2)	if(len%i==0){
		for(cur=p[i],x=l;x<=r;x+=i)	cur&=c[x][x+i-1];
		ret=(ret+solve(i,cur,1))%mod;
	}
	return ret;
}		

int main(){
	//freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
	int i,j;
	init();
	scanf("%s",s+1);n=strlen(s+1);
	rep(i,1,n)	a[i]=s[i]-'0';
	for(i=n;i;i--)	rep(j,i,n)	c[i][j]=(c[i+1][j]<<1)+(a[i]&1);
	rep(i,1,n)	rep(j,i,n)	g[i][j]=getG(i,j);
	dp[0][0]=1;
	rep(i,0,n-1) rep(j,i+1,n) dp[0][j]=(dp[0][j]+1ll*dp[0][i]*g[i+1][j])%mod;
	printf("%d\n",dp[0][n]);
}
			
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	

Measured memory_bytes: 76032
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+10;
ll n,a[N],prime[N],k,vis[N];//RE就开小一点
int flag=0;
bool isprime[N];
void Prime(){
    fill(isprime,isprime+N,1);
    k=0;
    prime[1]=0;
    for(ll i=2;i<N;i++){
        if(isprime[i]){
            prime[k++]=i;
            for(ll j=2;i*j<N;j++)
                isprime[i*j]=0;
        }
    }
}

//质因子分解找因子数
void solve(ll n){
    for(ll i=0;i<k&&prime[i]*prime[i]<=n;i++){
        if(n%prime[i]==0){
            if(vis[prime[i]]==0) vis[prime[i]]=1;
            else{
                flag=1;
                return;
            }
            while(n%prime[i]==0){
                n/=prime[i];
            }
        }
    }
    if(n>1){
         if(vis[n]==0) vis[n]=1;
        else{
            flag=1;
            return;
        }
    }
}

inline ll gcd(ll a,ll b)
{
    if(!b) return a;
    else{
        while(1){
            ll t=a%b;
            if(t==0) return b;
            else{
                a=b; b=t;
            }
        }
    }
}

int main(){
    Prime();
    cin>>n;
    ll GCD=0;
    for(int i=0;i<n;i++){
        scanf("%lld",&a[i]);
        if(!flag) solve(a[i]);
        if(GCD==0) GCD=a[i];
        else GCD=gcd(GCD,a[i]);
    }
    if(!flag) printf("pairwise coprime");
    else if(flag&&GCD==1) printf("setwise coprime");
    else printf("not coprime");
}




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

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

	vector<string> v_s(n);
	for (int i = 0; i < n; i++)
	{
		cin >> v_s[i];
	}


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

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

	cout << count << endl;


	return 0;
}




Measured memory_bytes: 9596
#include<iostream>
#include <cstdlib>
using namespace std;
int main(){
  string S;
  cin >> S;
  if(stoi(S.substr(0,2)) <= 12 && stoi(S.substr(0,2)) >= 1){
    if(stoi(S.substr(2,2)) <= 12 && stoi(S.substr(2,2)) >= 1){
      cout << "AMBIGUOUS" << endl;
    }else{
      cout << "MMYY" << endl;
    }
  }else{
    if(stoi(S.substr(2,2)) <= 12 && stoi(S.substr(2,2)) >= 1){
      cout << "YYMM" << endl;
    }else{
      cout << "NA" << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 384
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);
#define FO cout.tie(NULL);
#define FI cin.tie(NULL);
#define IN cin>>
#define OUT cout<<
#define loop(i,a,n) for(int i=a; i<n; i++)
#define rloop(i,a,n) for(int i=a; i>=n; i--)
#define endl "\n";
#define pb push_back
#define mp make_pair
#define set_bits(a) __builtin_popcount(a)
#define ll long long int
#define ld long double
#define vll vector<long long int>
#define pll pair<long long int, long long int>
#define mod 1000000007
#define M 998244353
ll gcd(ll a, ll b)
{
    return (b?gcd(b,a%b):a);
}
ll P(ll B, ll power, ll modulo)
{
    ll ans=1LL;
    while(power>0LL)
    {
        if(power%2LL==1LL)
        {
            ans=(ans*B)%modulo;
        }
        B=(B*B)%modulo;
        power/=2LL;
    }
    return ans;
}
bool isPrime(ll n)
{
    if(n<=1LL)
    {
        return false;
    }
    if(n<=3LL)
    {
        return true;
    }
    if(n%2==0LL || n%3==0LL)
    {
        return false;
    }
    for(ll i=5LL; (i*i)<=n; i+=6LL)
    {
        if(n%i==0LL || n%(i+2LL)==0LL)
        {
            return false;
        }
    }
    return true;
}
using namespace std;
bool sortbysec(const pair<int,int> &a, const pair<int,int> &b)
{
    return (a.second<b.second);
}
bool sortbysecll(const pll &a, const pll &b)
{
    return (a.second<b.second);
}
ll modinv(ll x, ll y, ll modulo)
{
    return ((x%modulo)*(P(y,modulo-2LL,modulo)%modulo))%modulo;
}
int main()
{
    FAST
    FO
    FI
    long double a,b,c;
    IN a>>b>>c;
    if((c)>(a+b+(2*sqrt(a*b))))
    {
        OUT "Yes"<<endl
    }
    else
    {
        OUT "No"<<endl
    }
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MOD 1000000007
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int N, M;
int dp[303][303][303];
vector<pair<int, int> > cond[330];
int lo[330][3], hi[330][3];

int main()
{
	scanf("%d%d", &N, &M);
	for (int i = 0; i <= N; ++i) {
		for (int j = 0; j < 3; ++j) {
			lo[i][j] = 1000;
			hi[i][j] = -1;
		}
	}
	for (int i = 0; i < M; ++i) {
		int l, r, x;
		scanf("%d%d%d", &l, &r, &x);
		cond[r].push_back({ l, x });

		lo[r][x - 1] = min(lo[r][x - 1], l);
		hi[r][x - 1] = max(hi[r][x - 1], l);
	}
	dp[0][0][0] = 1;
	int ret = 0;
	for (int i = 0; i <= N; ++i) {
		for (int j = 0; j <= N; ++j) {
			for (int k = 0; k <= N; ++k) {
				int mx = max({ i, j, k });

				int snd, thrd;
				if (i == mx) {
					snd = max(j, k);
					thrd = min(j, k);
				} else if (j == mx) {
					snd = max(i, k);
					thrd = min(i, k);
				} else {
					snd = max(i, j);
					thrd = min(i, j);
				}
				if (hi[mx][2] > thrd) goto fail;
				if (lo[mx][1] <= thrd) goto fail;
				if (hi[mx][1] > snd) goto fail;
				if (lo[mx][0] <= snd) goto fail;


				if (mx == N) ADD(ret, dp[i][j][k]);
				else {
					++mx;
					ADD(dp[mx][j][k], dp[i][j][k]);
					ADD(dp[i][mx][k], dp[i][j][k]);
					ADD(dp[i][j][mx], dp[i][j][k]);
				}
			fail:
				dp[i][j][k] = 0;
			}
		}
	}
	printf("%d\n", ret);

	return 0;
}


Measured memory_bytes: 108800
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) for (int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define MOD 1000000007
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
const int INFTY =2147483647;
int main(){
    string s;
    cin>>s;
    if(s.compare("ABC")==0) cout<<"ARC"<<endl;
    else cout<<"ABC"<<endl;
}

Measured memory_bytes: 3508
package main

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

func main() {
	n, m := readI(), readI()
	city := newUF(n)
	for i := 0; i < m; i++ {
		a, b := readI(), readI()
		a--
		b--
		city.unite(a, b)
	}
	g := 0
	for _, v := range city.d {
		if v < 0 {
			g++
		}
	}
	fmt.Println(g - 1)
}

// Union-Find Tree
type unionFind struct {
	d []int
}

// n is number of vertex
func newUF(n int) *unionFind {
	d := make([]int, n)
	for i := range d {
		d[i] = -1
	}
	u := unionFind{d}
	return &u
}

func (u *unionFind) root(a int) int {
	if u.d[a] < 0 {
		return a
	}
	u.d[a] = u.root(u.d[a])
	return u.d[a]
}

func (u *unionFind) unite(a, b int) {
	ar, br := u.root(a), u.root(b)
	if ar == br {
		return
	}
	if -u.d[ar] < -u.d[br] {
		ar, br = br, ar
	}
	u.d[ar] += u.d[br]
	u.d[br] = ar
}

func (u *unionFind) isSame(a, b int) bool {
	return u.root(a) == u.root(b)
}

func (u *unionFind) size(a int) int {
	return -u.d[u.root(a)]
}

/*-----------Input utils-----------*/

var sc = bufio.NewScanner(os.Stdin)

func init() {
	if len(os.Args) >= 2 {
		if os.Args[1] == "debug" {
			debug()
		}
	}
	const buf = 200100
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, buf), buf)
}

func debug() {
	testFile, err := os.Open("./test/sample-1.in")
	if err != nil {
		fmt.Fprintln(os.Stderr, "There is no testfile.")
		os.Exit(1)
	}
	sc = bufio.NewScanner(testFile)
}

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

func readR() []rune {
	return []rune(readS())
}

func readI() int {
	i, _ := strconv.Atoi(readS())
	return i
}

func readF() float64 {
	f, _ := strconv.ParseFloat(readS(), 64)
	return f
}


Measured memory_bytes: 3908
use std::io;
use std::cmp::min;

fn main() {
    let stdin = io::stdin();
    let mut buf = String::new();
    stdin.read_line(&mut buf).ok();
    let bytes = buf.as_bytes();

    let mut ans = 10000;
    for i in 0..bytes.len() - 3 {
        let now =
              (bytes[i] as i32 - b'0' as i32) * 100
            + (bytes[i+1] as i32 - b'0' as i32) * 10
            + (bytes[i+2] as i32 - b'0' as i32);
        
        ans = min(ans, (now - 753).abs());
    }
    println!("{}", ans);
}

Measured memory_bytes: 4352
const fs = require('fs');

const main = (input) => {
  const tail = input.slice(1);

  const money = tail
    .map(x => x.split(' '))
    .map(arr => conv(Number(arr[0]), arr[1]))
    .reduce((acc, x) => acc + x, 0);

  console.log(money);
};

const conv = (n, type) => {
  if (type === 'JPY') {
    return n;
  } else if (type === 'BTC') {
    return n * 380000.0;
  }
};

main(fs.readFileSync('/dev/stdin', 'utf8').trim().split('\n'));


Measured memory_bytes: 7372
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i)
#define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i)
#define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using Graph = vector<vector<int>>;
using P = pair<int, int>;

ll modnum = 1000000007;

long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}


int main() {
    double long l; cin >> l;

    double long t = l/3.00000;

    double long ans = t*t*t;

    cout << fixed<<std::setprecision(10) << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int f[100001];
int h[100001];
int main()
{
	int n,i,j,k;
	scanf("%d %d",&n,&k);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&h[i]);
	}
	f[1]=0;
	for(i=2;i<=n;i++)
	{
		f[i]=INT_MAX;
		for(j=1;i-j>0&&j<=k;j++)
		{
			f[i]=min(f[i-j]+abs(h[i]-h[i-j]),f[i]);
		}
	}
	printf("%d",f[n]);
	return 0;
}

Measured memory_bytes: 1024
#include<stdio.h>
#define N 100
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n, G[N][N];
int color[N], d[N], f[N], tt;

void dfs_vi(int u){
    int v;
    color[u] = GRAY;
    d[u] = ++tt;
    for(v = 0; v < n; v++) {
        if( G[u][v] == 0 ) {
          continue;
        }
        if( color[v] == WHITE ) {
          dfs_vi(v);
        }
    }
        color[u] = BLACK;
        f[u] = ++tt;
}

void dfs(void){
    int u;

    for( u = 0; u < n; u++ ) {
      color[u] = WHITE;
    }
    tt = 0;

    for( u = 0; u < n; u++ ) {
        if( color[u] == WHITE ) dfs_vi(u);
    }
    for( u = 0; u < n; u++ ) {
        printf("%d %d %d\n", u+1, d[u], f[u]);
    }
}

int main(){
    int u,v,k,i,j;

    scanf("%d", &n);
    for(i = 0; i < n; i++)
        for(j = 0; j < n; j++)
            G[i][j] = 0;

    for(i = 0; i < n; i++){
        scanf("%d %d", &u, &k);
        u--;
        for(j = 0; j < k; j++){
            scanf("%d", &v);
            v--;
            G[u][v] = 1;
        }
    }

    dfs();

    return 0;

}



Measured memory_bytes: 2108
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;

string dw[7] = { "thu", "fri", "sat", "sun", "mon", "tue", "wed" }; // 木金土日月火水

int main() {
    int x;
    cin >> x;
    cout << dw[x % 7] << endl;
}


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

int main()
{
	string S, T;
	cin >> S >> T;
	int cnt = 0;
	for (int i = 0; i < 3; i++) {
		cnt += S[i] == T[i];
	}
	cout << cnt << endl;
	return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <bitset> 
#include <vector>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
 
#define int long long
#define ll long long 
#define F first
#define sqr(x) ((x) * (x))
#define S second
#define make make_pair
#define pb push_back
#define sz(x) (ll)(x.size()) 
#define all(x) x.begin (), x.end ()

using namespace std;
                        
typedef unsigned long long ull;
typedef long double ld;

const int MOD = (int)1e9 + 7;
const int N = (int)2e6+ 222;
const ll INF = (ll)1e18;
const double eps = (double)1e-6;
                                    
string s, a[] = {"SUN", "MON", "TUE", "WED", "THU", "FRI","SAT"};


void solve () {                     
	cin >> s;
	for (int i = 0; i <= 6; ++i) {
		if (s == a[i]) {
			 	cout << 7 - i;
			 	return;
		}

	}
}



signed main () {
    #ifdef Maga
        freopen("input", "r", stdin);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);                                              
    int t = 1;
   // cin >> t;
    while (t --) {
    	solve ();
    }
    return 0;
}





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

using namespace std;

int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}

int main() {
  int A, B, C;
  cin >> A >> B >> C;
  int ac = gcd(A, C);
  if (B % ac == 0) {
    A /= ac;
    B /= ac;
  }
  cout << (gcd(A, B) == 1 ? "YES" : "NO") << endl;
}

Measured memory_bytes: 256
def bakudanda (y,x):
  if y < 0 or y >= len(s):
    return 0
  if x < 0 or x >= len(s[y]):
    return 0
  if s[y][x] == '#':
    return 1
  else:
    return 0
H,W = map(int,input().split())
s=[]
for i in range(H):
  s.append(input())
  
for i in range(len(s)):
  a = s[i]
  fp = ''
  for j in range(len(a)):
    if a[j] == '.':
      c = 0
      ds = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0,1), (1, -1), (1, 0), (1, 1)]
      for (y, x) in ds:
        c+= bakudanda(i+y,j+x)
      fp += str(c)
    else:
      fp += '#'
  print(fp)
        


Measured memory_bytes: 9220
#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

int main()
{
	int A,B,C,X;
	cin>>A>>B>>C>>X;
	int sum = 0;
	for(int i=0 ; i<=A ; i++)
	{
		for(int j=0 ; j<=B ; j++)
		{
			for(int k=0 ; k<=C ; k++)
			{
				if(500*i + 100*j + 50*k == X)sum++;
			}
		}
	}
	cout<<sum<<endl;
	
	return 0;
}

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

using namespace std;

#define ll long long
#define pi pair<int, int>
#define mkp make_pair
#define pb push_back
#define fr first
#define sc second
#define endl '\n'

const int mxn = 1e6 + 5;
const ll MOD =  1e9 + 7;
int arr[mxn];
int n, m, k;
ll l, r;
string s;

ll POW(ll A,ll B,ll R=1)
{while(B){if(B&1)R=R*A%MOD;A=A*A%MOD;B>>=1;}return R;}

void read(){
    //cin >> s;
//    for(int i = 0, u, v; i < n; i++){
//        cin >> arr[i];
//    }
}


void solve(){
    cin >> n >> k;
    set<int> st;
    for(int i = 0; i < k; i++){
        int d;
        cin >> d;
        while(d--){
            cin >> m;
            st.insert(m);
        }
    }
    cout << n - st.size() << endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    //cin >> T;
    while(T--) read(), solve();
    return 0;
}


Measured memory_bytes: 3660
while True:
    a,op,b = input().split()
    a = int(a)
    b = int(b)
    if op == '+':
        print(a+b)
    elif op == '-':
        print(a-b)
    elif op == '*':
        print(a*b)
    elif op == '/':
        print(a//b)
    else:
        break


Measured memory_bytes: 5596
#include<bits/stdc++.h>
#include<string.h>
using namespace std;
int main()
{
    int a,b,c,i=a,count=0;
    cin>>a>>b>>c;
    for(int i=a;i<=b;i++)
    {
       if(i%c==0)
       count++;
    }
    cout<<count<<endl;
    return 0;
}

Measured memory_bytes: 3584
#include <iostream>
#include<string>
#include<algorithm>
#include<stdio.h>

using namespace std;

int main(){
    int a[3];
    cin>>a[0]>>a[1]>>a[2];
    sort(a,a+3);

    if(a[0]+a[1]==a[2])cout<<"Yes"<<endl;
    else cout<<"No"<<endl;

    return 0;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define rep(i, s, n) for (int i = s; i < n; i++)
#define rrep(i, s, n) for (int i = (n)-1; i >= (s); i--)
#define all(a) a.begin(),a.end()
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
const long long MOD = 1000000007, INF = 1e17;
 
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)
 
template<class T>inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template<class T>inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}



signed main()
{
	//IOS();
	vector<double>ans;
	while(1){
		int D,E;
		cin>>D>>E;
		if(D == 0 && E == 0)break;
		double mi = INF;
		rep(i,0,D){
			int j = D - i;
			chmin(mi,abs(E-hypot(i,j)));
		}
		ans.push_back(mi);
	}
	for(auto e:ans){
		printf("%.20lf\n",e);
	}
}



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

using namespace std;

const int Maxn = 1e6+7;
const int Maxq = 80;

int n, Q, k;
int sm[Maxn], sc[Maxn];
long long sp[Maxn];
string S;

int main()
{
    cin >> n >> S >> Q;
    for(int i = 0; i < n; ++i)
    {
        sm[i+1] = sm[i]+(S[i] == 'M');
        sc[i+1] = sc[i]+(S[i] == 'C');
        sp[i+1] = sp[i]+(S[i] == 'C' ? sm[i+1]: 0);
    }
    while(Q--)
    {
        cin >> k;
        long long ans = 0;
        for(int a = 1; a <= n-2; ++a)
            if(S[a-1] == 'D')
                ans += (sp[min(n, a+k-1)]-sp[a]
                        -1ll*sm[a]*(sc[min(n, a+k-1)]-sc[a]));
        cout << ans << endl;
    }
    return 0;
}

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

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)

using ll = int64_t;

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

	int n; cin >> n;
	int h[n], ans[n]; rep(i, 0, n) cin >> h[i];
	ans[0] = 0;
	ans[1] = abs(h[1] - h[0]);
	rep(i, 2, n)
		ans[i] = min(ans[i - 1] + abs(h[i] - h[i - 1]),
			ans[i - 2] + abs(h[i] - h[i - 2]));
	cout << ans[n - 1];
}

Measured memory_bytes: 1024