akhauriyash/Code-Regression huggingface dataset:
l1 = [1, 3, 5, 7, 8, 10, 12]
l2 = [4, 6, 9, 11]

x, y = map(int, input().split())
flg = x in l1 and y in l1 or x in l2 and y in l2
print("Yes" if flg else "No")

Measured memory_bytes: 9184
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;

int main(){
  int N;cin>>N;
  vi table;
  for (int i=1;i<=15000;++i){table.push_back(2*i);}
  for (int i=0;i<5000;++i){table.push_back(3+6*i);}
  
  if(N==3){cout << 2 <<' ' << 3<< ' ' << 25; return 0;}
  if(N==4){cout << 2 <<' ' << 3<< ' ' << 25<< ' ' << 30; return 0;}
  if(N==6){cout << 2 <<' ' << 3<< ' ' << 25<< ' ' << 30<< ' ' << 60 << ' ' << 90; return 0;}
  if(N<=15000){
    if (N%3==1){
      cout << 3 << ' '<< 9<< ' ' << 15 << ' ' <<21 << ' ';
      for (int i=1;i<=N-4;++i){
        cout << 2*i << ' ';
      }
      return 0;
    }
  
    if(N%3==2){
      cout << 3 << ' ' << 9 << ' ';
      for (int i=1;i<=N-2;++i){
        cout << 2*i << ' ';
      }
      return 0;
    }
    if(N%3==0){
      cout << 3 << ' ' << 9 << ' ' << 15 << ' ' << 21 << ' ' << 27 << ' ' << 33 << ' ';
      for (int i=1;i<=N-6;++i){
        cout << 2*i << ' ';
      }
      return 0;
    }
  }

  if(N%2==0){
    for (int i=0;i<N;++i){
      cout << table[i] << ' ';
    }
    return 0;
  }
  if(N%2==1){
    for (int i=0;i<14999;++i){
      cout << table[i] << ' ';
    }
    for (int i=0;i<N-14999;++i){
      cout << table[15000+i] << ' ';
    }
    return 0;
  }
}


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

int main() {
    while (1) {
        int N;
        cin >> N;
        if (N == 0) break;
        double score[N];
        double sum1 = 0;
        for (int i = 0; i < N; i++) {
            cin >> score[i];
            sum1 += score[i];
        }
        double M = sum1 / double(N);
        double sum2 = 0;
        for (int i = 0; i < N; i++) sum2 += pow(score[i] - M, 2);
        double V = sum2 / double(N);
        double A = sqrt(V);
        cout << fixed << setprecision(6) << A << endl;
    }
}


Measured memory_bytes: 3280
length, max_length = 0, 0
s = input()

for c in s:
    if c == 'A' or c == 'C' or c == 'G' or c == 'T':
        length += 1
    else:
        max_length = max(max_length, length)
        length = 0
max_length = max(max_length, length)

print(max_length)


Measured memory_bytes: 2940
#include <iostream>
#include <string>

using namespace std;


int main() {

	string inp;
	cin >> inp;

	bool next_h = true;
	bool next_i = false;
	for (char a : inp)
	{
		if (next_h && a == 'h') {
			next_h = false;
			next_i = true;
		}
		else if(next_i && a == 'i'){
			next_h = true;
			next_i = false;
		}
		else {
			cout << "No" << endl;
			return 0;
		}
	}

	if (next_h) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

	return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int lld;

const lld N = 200043;
const lld MOD = 998244353;

lld add(lld x, lld y)
{
    x =((x%MOD)+(y%MOD))%MOD;
    while(x >= MOD) x -= MOD;
    while(x < 0) x += MOD;
    return x;
}

lld mul(lld x, lld y)
{
    return ((x%MOD)*(y%MOD))% MOD;
}

lld binpow(lld x, lld y)
{
    lld z = 1;
    while(y)
    {
        if(y & 1) z = mul(z, x);
        x = mul(x, x);
        y >>= 1;
    }
    return z;
}

lld inv(lld x)
{
    return binpow(x, MOD - 2);
}

lld divide(lld x, lld y)
{
    return mul(x, inv(y));
}

// Combinations

lld fact[N];

void precalc()
{
    fact[0] = 1;
    for(lld i = 1; i < N; i++)
        fact[i] = mul(fact[i - 1], i);
}

lld C(lld n, lld k)
{
    return divide(fact[n], mul(fact[k], fact[n - k]));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lld t,i,j;
    //cin>>t;
    t=1;
    precalc();
    while(t--)
    {
        lld n,m,k;
        cin>>n>>m>>k;
        lld ans=0;
        for(i=0;i<=k;i++)
        {
            ans=add(ans,mul(mul(m,binpow(m-1,n-1-i)),C(n-1,i)));
        }
        cout<<ans<<endl;
    }
}




Measured memory_bytes: 5216
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000000007;
int main()
{
    string s,t;
    cin >> s >> t;
    for(int i = 0;i < s.size();i++)
    {
        if(s[i] != t[i])
        {
            cout << "No\n";
            return 0;
        }
    }
    cout << "Yes\n";
    
    return 0;
}

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

int main(){
    int n,m; cin >> n >> m;
    vector<P> ans;
    if(n%2){
        for(int l=1,r=n-1;l<r;++l,--r){
            ans.emplace_back(l,r);
        }
    }
    else{
        bool flag = false;
        for(int l=1,r=n-1;l<r;++l,--r){
            if(!flag && r-l <=n/2){
                ++l;
                flag = true;
            }
            ans.emplace_back(l,r);
        }
    }
    rep(i,m){
        printf("%d %d\n",ans[i].first,ans[i].second);
    }
    return 0;
}

Measured memory_bytes: 4216
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())
#define endl "\n"
template<class T> void chmax(T &a, const T b){ a = max(a, b); }
template<class T> void chmin(T &a, const T b){ a = min(a, b); }

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // ifstream in("input.txt");
    // cin.rdbuf(in.rdbuf());
    ll n, q;
    cin >> n >> q;
    dsu d(n);
    rep(i, q) {
        ll t, u, v;
        cin >> t >> u >> v;
        if (t == 0) {
            d.merge(u, v);
        }
        else {
            cout << (d.same(u, v) ? 1 : 0) << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3936
s = input()
K = int(input())
a = sorted(set(s))
ans = set()

for i in a:
    for j in range(len(s)):
        if s[j] == i:
            for k in range(5):
                ans.add(s[j:j + k + 1])
    if len(ans) >= K:
        print(sorted(list(ans))[K - 1])
        exit()

Measured memory_bytes: 3060
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

n, m = [int(i) for i in input().split()]
X = [[int(i) for i in input().split()] for j in range(m)]

E = [[] for i in range(n+1)]

for a, b in X:
    E[a].append(b)

memo = [-1] * (n+1)

def dfs(i):
    if memo[i] != -1:
        return memo[i] + 1
    if not E[i]:
        return 0

    memo[i] = max(dfs(e) for e in E[i])
    return memo[i] + 1

print(max(dfs(i) for i in range(1, n+1)))

Measured memory_bytes: 119116
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(),v.end()
#define INF 1e9
typedef long long ll;
using namespace std;

int main() {
    int s; cin >> s;
    int ans = 1;
    while(ans*2<=s){
        ans*=2;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		
		/* ＜考察＞
		 * 9589,9479 9599は8999の方が大きいし、9479は8999の方がやはり値が大きい。
		 * 9が出来るだけ多く出るようにしたい。その次に８が多くなるように数字を出すには...。
		 * ex)4桁の場合
		 * 8245などは一番左のけたを1減らすことによりそれ以降を全部9に変えることが出来る。
		 * 	これが最適では？
		 * 
		 * かといって8999のようなときに桁をずらす必要はないため最適な状況を除いて一番左だけーにする。						
		*/		
		
		
		String n = stdIn.next();
		
		if(n.length()==1) {
			System.out.println(n);
			return;
		}
		
		String numb = "";
		for(int i = 0; i < n.length()-1; i++) {
			numb +="9";
		}
		long n2 = Long.parseLong(n);
		
		String n3 = n.substring(1);
		long ans = 0;
		
		
		if(numb.equals(n3)) {
			while(n2 > 0) {
				ans += n2%10;
				n2/=10;
			}
			System.out.println(ans);
			return;
		}
		
		
		
		int num = Integer.parseInt(n.substring(0,1));
		
		num--;
		
		if(num== 0) {
			ans = (long)9*(n.length()-1); 
		}
		
		
		ans = Math.max(ans,num+(9*(n.length()-1)));
		
		System.out.println(ans);
		
		
		
		
		
	}

}


Measured memory_bytes: 21460
#include <iostream>

using namespace std;

class DLL {

private:
    typedef struct NodeData {
        NodeData * next;
        NodeData * prev;
        int key;
        NodeData(int newKey) {
            next = nullptr;
            prev = nullptr;
            key = newKey;
        }
        ~NodeData() { }
    }* Node;

    Node root;

public:
    DLL(void);
    void insert(int);
    void deleteKey(int);
    void deleteFirst(void);
    void deleteLast(void);
    void printList(void);
    ~DLL(); 
};

DLL::DLL(void)
{
    root = new NodeData(0);
    root->next = root;
    root->prev = root;
}

DLL::~DLL()
{
    Node node = root->next, nextNode;
    while (node != root) {
        nextNode = node->next;
        delete node;
        node = nextNode;
    }
    delete root;
};

void DLL::insert(int key)
{
    Node newNode = new NodeData(key);
    newNode->next = root->next;
    newNode->prev = root;
    
    root->next->prev = newNode;
    root->next = newNode;
}

void DLL::deleteKey(int key)
{
    Node node = root->next;
    while (node != root && node->key != key)
        node = node->next;

    if (node != root) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
        delete node;
    }
}

void DLL::deleteFirst(void)
{
    if (root->next != root) {
        Node temp = root->next;
        root->next->next->prev = root;
        root->next = root->next->next;
        delete temp;
    }
}

void DLL::deleteLast(void)
{
    if (root->prev != root) {
        Node temp = root->prev;
        root->prev->prev->next = root;
        root->prev = root->prev->prev;
        delete temp;
    }
}

void DLL::printList(void)
{
    if (root->next != root) {
        cout << root->next->key;
        for (Node node = root->next->next; node != root; node = node->next)
            cout << " " << node->key; 
        cout << endl;
    }
}

int main(void)
{
    size_t n;
    DLL dlist; 
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;

    for (size_t i = 0; i < n; i++) {
        string buf;
        cin >> buf;
        if (buf == "insert") {
            int key; cin >> key;
            dlist.insert(key);
        } else if (buf == "delete") {
            int key; cin >> key;
            dlist.deleteKey(key);
        } else if (buf == "deleteFirst")
            dlist.deleteFirst();
        else if (buf == "deleteLast")
            dlist.deleteLast();
        else {
            cout << "Invalid input";
            exit(-1);
        }
    }

    dlist.printList();

    return 0;
}

Measured memory_bytes: 32492
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


# aとbの最大公約数
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

# aとbの最小公倍数
def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def main():
    N = int(input())
    if N == 1:
        print("Hello World")
    else:
        A = int(input())
        B = int(input())
        print(A + B)


if __name__ == '__main__':
    main()


Measured memory_bytes: 4196
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    int n, k, a, b = 0;
    ll z = 0;
    map<int, int> m; m[0] = 1;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a, b = (b + a) % k, z += m[b], m[b]++;
    cout << z;
}


Measured memory_bytes: 3200
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));



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



	int x, y ,z;
	cin >> x >> y>>z;

	if ((100*x+10*y+z)%4==0) {
		cout <<"YES"<< endl;
	}
	else
		cout << "NO" << endl;
	
	return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
using namespace std;
typedef long long ll;
int main(){
  string s;
  cin>>s;
  int k=s.length();

  int cn=0;
  for(int i=0;i<k;i++){
    char a=s[i];
    if(a=='x') cn++;
  }
  cout<<(cn>7?"NO":"YES")<<endl;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
        int a,b,c,x;
        cin >> a >> b >> c >> x;

        int ans=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) ans++;
                        }
                }
        }

        cout << ans << endl;

        return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const long long mod=1000000007;
char in[1100][1100];
long long dp[1100][1100];
int main(){
    int a,b;
    cin>>a>>b;
    for(int i=0;i<a;i++){
        
        cin>>in[i];
    }
    dp[0][0]=1;
    for(int i=0;i<a;i++){
        for(int j=0;j<b;j++){
            if(in[i][j]=='#')continue;
            if(i-1>=0)dp[i][j]=(dp[i-1][j]+dp[i][j])%mod;
            if(j-1>=0)dp[i][j]=(dp[i][j-1]+dp[i][j])%mod;
        }
    }
    cout<<dp[a-1][b-1];
    return 0;
}

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

int main(){
    int H, W;
    cin >> H >> W;
    while( H != 0 ){
        int i, n, j, k;
        j = H - 1;
        k = W - 1;
        for( i = 0; i < H; i ++ ){
            if( i == 0 || i == j ){
                for( n = 0; n < W; n ++ ){
                    cout << "#";
                }
            }else{
                for( n = 0; n < W; n ++ ){
                    if( n == 0 || n == k ){
                        cout << "#";
                    }else{
                        cout << ".";
                    }
                }
            }
            cout << endl;
        }
        cout << endl;
        cin >> H >> W;
    }
    return 0;
}


Measured memory_bytes: 3100
fun main(args: Array<String>){
    val arr = readLine()!!.split(" ").map { s->s.toInt() }
    val A=arr[0]
    val B=arr[1]
    val Q=arr[2]
    val s = Array(A){readLine()!!.toLong()}
    val t = Array(B){readLine()!!.toLong()}
    val result = mutableListOf<Long>()
    for(i in 0 until Q){
        val x = readLine()!!.toLong()
        val si = -s.binarySearch(x)-1
        val ti = -t.binarySearch(x)-1
        if(si<A&&ti<B){
            result.add(Math.max(s[si],t[ti])-x)
        }
        if(si>0&&ti>0){
            result.add(x-Math.min(s[si-1],t[ti-1]))
        }
        if(si<A&&ti>0){
            result.add(s[si]*2-t[ti-1]-x)
            result.add(x+s[si]-t[ti-1]*2)
        }
        if(si>0&&ti<B){
            result.add(t[ti]*2-s[si-1]-x)
            result.add(x+t[ti]-s[si-1]*2)
        }
        println(result.min())
        result.clear()
    }
}

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

int findAngle(int hour, int min)
{
	// find position of hour's hand
	int h = (hour * 360) / 12 + (min * 360) / (12 * 60);

	// find position of minute's hand
	int m = (min * 360) / (60);

	// calculate the angle difference
	int angle = abs(h - m);

	// consider shorter angle and return it
	if (angle > 180)
		angle = 360 - angle;

	return angle;
}

int main(){
	double a,b,h,m,hang,mang,angle,c;
	cin>>a>>b>>h>>m;
	
	hang=0.5 * (h*60+m);
	mang=6*m;
	angle=hang-mang;
	angle=min(angle,360-angle);
	
	//angle=findAngle(h,m);
	c=sqrt(pow(a,2)+pow(b,2)-2*a*b*cos((angle/180)*M_PI));
	cout<<fixed<<setprecision(16)<<c<<endl;
}

Measured memory_bytes: 4216
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <list>
#include <numeric>
#include <map>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
//================================================

int a = 0, b = 0, c, d, n, k=0;
string s, t;


int main()
{
	int n,k;
	cin >> n >> k;
	int cnt = 1;
	while(n>=k)
	{
		n /= k;
		cnt++;
	}
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include<algorithm>
#include<string>
#include<vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <numeric>

using namespace std;

int main()
{
	int cnt = 0;
	string s;
	cin >> s;
	vector<char>setS(s.length());
	for (int i = 0; i < setS.size(); i++)setS[i] = s[i];
	sort(setS.begin(),setS.end());
	for (int i = 0; i < setS.size(); i++)s[i] = setS[i];
	for (int i = 0; i < setS.size(); i++) {
		if (s[i] == s[i + 1])cnt++;
		else if ((cnt + 1) % 2 == 0)cnt = 0;
		else {
			cout << "No" << endl; return 0;
		}
	}
	cout << "Yes" << endl;
}

Measured memory_bytes: 256
{-# LANGUAGE BangPatterns #-}

import Control.Monad
import Data.List
import Data.Bits
import Debug.Trace
import Data.Maybe
import qualified Data.ByteString.Char8 as C

main :: IO ()
main = do
  s <- getLine
  print $ solve s

solve = solveSub 0 0
  where
    solveSub maxlen len [] = max maxlen len
    solveSub maxlen len (x:xs) =
      if atgc x
        then solveSub maxlen (len + 1) xs
        else solveSub (max maxlen len) 0 xs

atgc b
  | b == 'A' = True
  | b == 'T' = True
  | b == 'G' = True
  | b == 'C' = True
  | otherwise = False

-- 以下ライブラリ

readInts :: IO [Int]
readInts = map (fst . fromJust . C.readInt) . C.words <$> C.getLine

readNInts :: Int -> IO [[Int]]
readNInts = flip replicateM readInts

readIntegers :: IO [Integer]
readIntegers = map (fst . fromJust . C.readInteger) . C.words <$> C.getLine

readNIntegers :: Int -> IO [[Integer]]
readNIntegers = flip replicateM readIntegers

getNLns :: Int -> IO [String]
getNLns = flip replicateM getLine

Measured memory_bytes: 380
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <limits>
#include <map>
#include <stack>
#include <unordered_map>
#define REP(i,n) for(long (i)=0;(i)<(n);(i)++)
#define REPI(i,a,b) for(long (i)=(a);(i)<(b);(i)++)
#define INF numeric_limits<double>::infinity()
constexpr long MOD = 1e9 + 7;
using namespace std;
using P = pair<long, long>;
using VI = vector<long>;

bool a[4];

int main() {
    string s;
    cin >> s;
    REP(i,s.size()) {
        if (s[i] == 'W') a[0] = true;
        if (s[i] == 'N') a[1] = true;
        if (s[i] == 'E') a[2] = true;
        if (s[i] == 'S') a[3] = true;
    }
    bool fl = true;
    REP(i,4) {
        fl *= a[i];
    }
    if (fl) {
        cout << "Yes" << endl;
    } else {
        if (a[0] && a[2] && (!a[1]) && (!a[3])) {
            cout << "Yes" << endl;
            return 0;
        }
        if ((!a[0]) && (!a[2]) && (a[1]) && (a[3])) {
            cout << "Yes" << endl;
            return 0;
        }
        cout << "No" << endl;
        
    }
}


Measured memory_bytes: 256
#!/Library/Frameworks/Python.framework/Versions/3.5/bin/python3

n = int(input())
h = list(map(int, input().split()))

ans = 0
cnt = 0
for i in range(1, len(h)):
    if h[i - 1] >= h[i]:
        cnt += 1
    else:
        ans = max(ans, cnt)
        cnt = 0

ans = max(ans, cnt)
print(ans)


Measured memory_bytes: 14252
import java.util.Scanner;

public class Main {

    /**
     * @param args
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            String s = new StringBuilder(sc.next()).reverse().toString();
            if (s.equals("#"))
                break;
            long a = 0;
            long b = 1;
            int n = 0, w = 0;
            char ch = s.charAt(0);
            int ii = 0;
            if (ch == 'h') {
                a = 0;
                n++;
                ii = 5;
            } else {
                a = 90;
                w++;
                ii = 4;
            }
            int cnt=1;
            for (int i = ii; i < s.length();) {
                ch = s.charAt(i);
                long c = 90, d = 0;
                d = (long) Math.pow(2, cnt);
                a = a * d;
                c = c * b;
                b = b * d;
                if (ch == 'h') {
                    a = a - c;
                    i += 5;
                } else {
                    a = a + c;
                    i += 4;
                }
                long gcd = gcd(a, b);
                a /= gcd;
                b /= gcd;
                cnt++;
            }
            if(b==1){
                System.out.println(a);
            } else {
                System.out.println(a+"/"+b);
            }
        }
    }

    static long gcd(long a, long b) {
        if (a < b) {
            long tmp = a;
            a = b;
            b = tmp;
        }
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

}

Measured memory_bytes: 17176
import java.util.*;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        sc.close();

        // 主処理
        int result = 0;
        for (int i = n; 0 < i; i--) {
            int root = (int) Math.sqrt(i);
            if (root * root == i) {
                result = i;
                break;
            }
        }

        // 出力
        System.out.println(result);
    }
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(long long i=0;i<x;i++)
#define repn(i,x) for(long long i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
vector<pair<string,P> >vec;
// vector<vector<int>> data(3, vector<int>(4));


void solve(long long M, vector<long long> d, vector<long long> c){

	ll D = 0, S = 0;
	rep(i, M) {
		D += c[i];
		S += d[i]*c[i];
	}
	cout << D-1+(S-1)/9 << endl;
	
}

int main(){	
	long long M;
	scanf("%lld",&M);
	vector<long long> c(M-1+1);
	vector<long long> d(M-1+1);
	for(int i = 0 ; i <= M-1 ; i++){
		scanf("%lld",&d[i]);
		scanf("%lld",&c[i]);
	}
	solve(M, d, c);
	return 0;
}



Measured memory_bytes: 6528
import bisect
n = int(input())
a = [int(input()) for i in range(n)][::-1]

color_num = [a[0]]
for i in range(1, n):
    if a[i] >= color_num[-1]:
        color_num.append(a[i])
    else:
        temp = bisect.bisect_right(color_num, a[i])
        color_num[temp] = a[i]


print(len(color_num))

Measured memory_bytes: 13728
//最小値を求めるのね…
#include <iostream>
#include <cassert>
#define int long long
using namespace std;

int n, s;

int f(int b, int n) {
	if (n < b) return n;
	return f(b, n / b) + n % b;
}

signed main() {
	cin >> n >> s;
	
	if (n == s) { cout << n + 1 << endl; return 0; }		//1桁
	if (n < s * 2 - 1) { cout << -1 << endl; return 0; }	//ダメ
	
	//3桁以上かも
	for (int i = 2; i * i <= n; i++) {
		if (f(i, n) == s) {
			cout << i << endl;
			return 0;
		}
	}
	
	//絶対に2桁
	int ans = 1145141919810;
	for (int i = 1; i * i <= n; i++) {	//2桁目を決め打ち
		if ((n - s) % i != 0 || s - i < 0 || s - i >= (n - s) / i + 1) continue;
		int b = (n - s) / i + 1;
		if (i >= b) { continue; }
		
		ans = min(ans, (n - s) / i + 1);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i = a;i < b;i++)
#define rrep(i,a,b) for(int i = a;i >= b;i--)
#define all(x) (x).begin(),(x).end()
#define fore(i,a) for(auto &i:a)
#define dbg(x) cerr << #x << ": " << x << endl;
typedef long long ll;
using namespace std;

//---------------------------------------------------------------------------------------------------




//---------------------------------------------------------------------------------------------------

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

   int flag = 1;

   rrep(i,s.size() - 1,0){
      if(s[i] == 'r' && s[i - 1] == 'e' && s[i - 2] == 'm' && s[i - 3] == 'a' && s[i - 4] == 'e' && s[i - 5] == 'r' && s[i - 6] == 'd') i -= 6;
      else if(s[i] == 'm' && s[i - 1] == 'a' && s[i - 2] == 'e' && s[i - 3] == 'r' && s[i - 4] == 'd') i -= 4;
      else if(s[i] == 'e' && s[i - 1] == 's' && s[i - 2] == 'a' && s[i - 3] == 'r' && s[i - 4] == 'e') i -= 4;
      else if(s[i] == 'r' && s[i - 1] == 'e' && s[i - 2] == 's' && s[i - 3] == 'a' && s[i - 4] == 'r' && s[i - 5] == 'e') i-=5;
      else flag = 0;
   }

   cout << (flag? "YES" : "NO") << endl;
   
   return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
long long gcd(long long a,long long b){
  if(a>b){swap(a,b);}
  if(a==0){return b;}
  else{return gcd(b%a,a);}
}
int main(){
  long long a,b;
  cin>>a>>b;
  cout<<a/gcd(a,b)*b;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
#define sz(i) (int)(i.size())
#define F first
#define S second
#define L long double
#define P pair<int, int>
const int inf = 0x3f3f3f3f3f3f3f3LL;
const int mod = (int)1e9 + 7;
using namespace std;
#if LOCAL
#include "../../tr.h"
#else
#define tr(...)
#define endl '\n'
#endif
template<class T> void smin(T& a, T val) {if (a > val) a = val;}template<class T> void smax(T& a, T val) {if (a < val) a = val;}
const int N = 5*(int)1e5 + 10;

int n;

std::vector<int> factors;
void factorize(int n){
   for (int i = 1; i*i <= n; ++i)
   {
      if(n%i)continue;
      if(i>1)
         factors.push_back(i);
      if(i != n/i){
         factors.push_back(n/i);
      }
   }
   sort(factors.begin(), factors.end());
}

bool check(int k){
   int t = n;
   tr(n, k);
   while(t >= k){
      if(t % k == 0)
         t /= k;
      else
         t %= k;
   }
   return t == 1;
}

void solve(){
   cin>>n;
   factorize(n);
   factorize(n-1);

   //make sure vector is sorted
   ((factors).erase(unique((factors).begin(), (factors).end()), (factors).end()));

   int ans = 0;
   tr(factors);
   for(auto it: factors){
      ans += check(it);
   }

   cout<<ans;
}

int32_t main(){_
   
   int t = 1;
   //cin >> t;

   while(t--){
     solve();
     cout << endl;
   }
   

   return 0;
}

Measured memory_bytes: 384
#include<iostream>

using namespace std;

int main(){
	int a;
  cin>>a;
  int l,r;
  l=a/100;
  r=a%100;
  if(l>=1 && l<=12){
  	if(r>=1 && r<=12){
    	cout<<"AMBIGUOUS\n";
    }
    else{
    	cout<<"MMYY\n";
    }
  }
  else{
  	if(r>=1 && r<=12 && l>=0){
    	cout<<"YYMM\n";
    }
    else{
    	cout<<"NA\n";
    }
  }
  return 0;
}

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


int main() {

	int N;
	cin >> N;
	vector<int> a(N);
	for (int i = 0;i < N;i++) {
		cin >> a.at(i);
	}

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

	int count = 0;
	for (int i = 0;i < N;) {
		int count_i_0 = 0;
		int count_i_1 = 0;
		int count_i = 0;
		for (int j = i;j < N;j++) {
			if (a.at(j) - a.at(i) ==0) {
				count_i_0++;
			}
			else
				break;
		}
		for (int k = i + count_i_0;k < N;k++) {
			if (a.at(k) - a.at(i) == 1) {
				count_i_1++;
			}
			else
				break;
		}
		if (i > 0) {
			for (int l = i - 1;l >= 0;l--) {
				if (a.at(i) - a.at(l) == 1) {
					count_i++;
				}
				else
					break;
			}
		}
		count = max(count, count_i_1+count_i_0 + count_i);
		i += count_i_0;
	}
	cout << count;
}


Measured memory_bytes: 640
#include<iostream>
using namespace std;
int main(){
	int n;
	cin>>n;
	int a[100][100]={0};
	for(int l=0; l<n; l++){
		int v,k;
		cin>>v>>k;
		int u;
		for(int i=0; i<k; i++){
			cin>>u;
			a[v-1][u-1]=1;
		}
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<n-1; j++){
			cout<<a[i][j]<<" ";
		}
		cout<<a[i][n-1]<<endl;
	}
	return 0;
}


Measured memory_bytes: 3136
#include <iostream>
#include <string>
#include <cctype>

using namespace std;

int main() {
	string s;

	getline(cin, s);

	for(int i = 0;i < s.size();i++) {
		if(isupper(s.at(i))) {
			s.at(i) = tolower(s.at(i));
		} else if(islower(s.at(i))) {
			s.at(i) = toupper(s.at(i));
		}
	}

	cout << s << endl;

	return 0;
}

Measured memory_bytes: 3144
#include<stdio.h>

main()
{
	int w,h,x,y,r;
	scanf("%d %d %d %d %d",&w,&h,&x,&y,&r);
	
	if(x+r>w || x-r<0 || y+r>h || y-r<0){
		printf("No\n");
	} else {
		printf("Yes\n");
	}
	
	return 0;
}

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

int main() {
	// your code goes here
	int n;
	cin>>n;
	string s;
	cin>>s;
	int total_w=0;
	int total_r=0;
	for(int i=0;i<n;i++){
		if(s[i]=='W'){
			total_w++;
		}
		else total_r++;
	}
	int t=n;
	int pre_w=0;
	int pre_r=0;
	for(int i=0;i<=n;i++){
		t=min(t,max(pre_w,total_r));
		if(i<n && s[i]=='W'){
			pre_w++;
			total_w--;
		}
		else if(i<n && s[i]=='R'){
			pre_r++;
			total_r--;
		}
		
	}
	cout<<t;
	return 0;
}

Measured memory_bytes: 3732
//2018.09.21 11min

#include <iostream>
using namespace std;

int main() {

    int n;
    cin >> n;

    int a[n];
    int i;
    int maxv=0, minv=2000000000;

    for(i=0;i<n;i++){
        cin >> a[i];
        maxv = max(maxv,a[i]);
        minv = min(minv,a[i]);
    }

    cout << maxv-minv << endl;

    return 0;
}

Measured memory_bytes: 256
package main

import "fmt"

func isEven(n int) bool { return n%2 == 0 }

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

	ans := 0

	x := n / k
	ans += x * x * x
	if isEven(k) {
		y := (n + k/2) / k
		ans += y * y * y
	}
	fmt.Println(ans)
}


Measured memory_bytes: 512
#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cmath>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
const int MAXN=5e5+5;
const int INF=1e9+5;
int read()
{
    int s=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
    return s*f;
}
ll arr[MAXN];
int main()
{
    string s;
    cin>>s;
    ll ans=0;
    ll cnt=1;
    int n=s.size();
    for(int i=n-1;i>=0;i--)
    {
        if(s[i]=='>')
        {
            arr[i]=cnt++;
        }
        else
        {
            cnt=1;
        }
    }
    cnt=0;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='<')
        {
            arr[i]=cnt++;
        }
        else
        {
            cnt=0;
        }
    }
    if(s[n-1]=='>')arr[n]=arr[n-1]-1;
    else arr[n]=arr[n-1]+1;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='<')
        {
            if(arr[i]>=arr[i+1])arr[i+1]=arr[i]+1;
        }
    }
    for(int i=0;i<=n;i++)ans+=arr[i];
    cout<<ans<<endl;
    return 0;
}
/*
< > > > < < > < < < < < > > > <
0 3 2 1 0 1 2 0 1 2 3 4 5 2 1 0 1
0       0 1   0 1 2 3 4       0 1
  3 2 1     1           3 2 1
0       0 1   0 1 2 3 4       0 1

*/


Measured memory_bytes: 4740
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[200005];
int main(){
    ll n,w;cin>>n>>w;
    ll weights[200005];
    ll prices[200005];
    for(ll i=0;i<n;i++){
        cin>>weights[i]>>prices[i];
    }

    

    for(ll i=0;i<n;i++){
        for(ll u=w;u>=weights[i];u--){
            dp[u]=max(dp[u],prices[i]+dp[u-weights[i]]);
        }
    }
    ll ans=0;
    for(ll i=0;i<=w;i++){
        ans=max(ans,dp[i]);
    }
    cout<<ans;
}

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

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

typedef long long ll;
typedef array<int, 3> tri;
typedef long double ld;

template <class T> istream& operator>>(istream& I, vector<T>& v) {for (T &e: v) I >> e; return I;}
template <class T> ostream& operator<<(ostream &O, const vector<T>& v) {for (const T &e: v) O << e << ' '; return O;}



void _main() {
        int n;
        cin >> n;
        int a[n + 1];
        for (int i = 1; i <= n; i++) cin >> a[i];


        vector<int> choice(n + 1);
        for (int i = n; i >= 1; i--) {
                if (i * 2 > n) {
                        choice[i] = a[i];
                } else {
                        int sum = 0;
                        int ts = 2;
                        while (ts * i <= n) {
                                (sum += choice[i * ts]) %= 2;
                                ts++;
                        }
                        if (sum != a[i]) choice[i] = 1;
                }
        }

        vector<int> ans;
        for (int i = 1; i <= n; i++) {
                if (choice[i]) ans.emplace_back(i);
        }

        cout << ans.size() << '\n' << ans;
}



signed main() {
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//        freopen("input.txt", "r", stdin);
        int _t = 1;
//        cin >> _t;
        while (_t--) _main();
        return 0;
}

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for(int i=0; i<n; i++) {
        cin >> a[i];
    }
    // dp[i] - TRUE if the first player wins if there are i stones left
    vector<bool> dp(k+1, false);
    for(int stones=0; stones<=k; stones++) {
        for(int x : a) {
            if(stones >= x && !dp[stones-x]) {
                dp[stones] = true;
            }
        }
    }
    /*
    for(int i=0; i<=k; i++) {
        cout << dp[i] << " ";
    }
    cout << endl;
    */
    cout << (dp[k]?"First":"Second");
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <climits>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <set>
#include <map>
#include <list>
#include <deque>
#include <vector>
#include <string>
#include <bitset>
#define y0 qvya13579
#define y1 qvyb24680
#define j0 qvja13579
#define j1 qvjb24680
#define next qvne13579xt
#define prev qvpr13579ev
#define INF 1000000007
#define PI acos(-1.0)
#define endl "\n"
#define IOS cin.tie(0);ios::sync_with_stdio(false)
#define M_P make_pair
#define P_B push_back
#define U_B upper_bound
#define L_B lower_bound
#define P_Q priority_queue
#define FIR first
#define SEC second
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REP_R(i,n) for(int i=((int)(n)-1);i>=0;--i)
#define FOR(i,m,n) for(int i=((int)(m));i<(int)(n);++i)
#define FOR_R(i,m,n) for(int i=((int)(m)-1);i>=(int)(n);--i)
#define ALL(v) (v).begin(),(v).end()
#define RALL(v) (v).rbegin(),(v).rend()
#define SIZ(x) ((int)(x).size())
#define COUT(x) cout<<(x)<<endl
#define CIN(x) cin>>(x)
#define CIN2(x,y) cin>>(x)>>(y)
#define CIN3(x,y,z) cin>>(x)>>(y)>>(z)
#define CIN4(x,y,z,w) cin>>(x)>>(y)>>(z)>>(w)
#define SCAND(x) scanf("%d",&(x))
#define SCAND2(x,y) scanf("%d%d",&(x),&(y))
#define SCAND3(x,y,z) scanf("%d%d%d",&(x),&(y),&(z))
#define SCAND4(x,y,z,w) scanf("%d%d%d%d",&(x),&(y),&(z),&(w))
#define SCANLLD(x) scanf("%lld",&(x))
#define SCANLLD2(x,y) scanf("%lld%lld",&(x),&(y))
#define SCANLLD3(x,y,z) scanf("%lld%lld%lld",&(x),&(y),&(z))
#define SCANLLD4(x,y,z,w) scanf("%lld%lld%lld%lld",&(x),&(y),&(z),&(w))
#define PRINTD(x) printf("%d\n",(x))
#define PRINTLLD(x) printf("%lld\n",(x))
typedef long long int lli;
using namespace std;

int ctoi(char c)
{
  if( c >= '0' and c <= '9' )
    {
      return (int)(c-'0');
    }

  return -1;
}

int alphabet_pos(char c) 
{
  if( c >= 'a' and c <= 'z' )
    {
      return (int)(c-'a');
    }

  return -1;
}


int alphabet_pos_capital(char c)
{
  if( c >= 'A' and c <= 'Z' )
    {
      return (int)(c-'A');
    }

  return -1;
}


vector<string> split(string str, char ch)
{
  int first = 0;
  int last = str.find_first_of(ch);
  
  if(last == string::npos)
    {
      last = SIZ(str);
    }

  vector<string> result;

  while( first < SIZ(str) )
    {
      string Ssubstr(str, first, last - first);
      result.push_back(Ssubstr);
      first = last + 1;
      last = str.find_first_of(ch, first);

      if(last == string::npos)
	{
	  last = SIZ(str);
	}
    }
  
  return result;
}

/*--------------- the end of the template --------------------*/









int main()
{
  IOS; /* making cin faster */
  string S;
  CIN(S);
  int cnt_C = 0;
  int cnt_oth = 0;
  
  REP(i,SIZ(S))
    {
      if( alphabet_pos_capital(S[i]) == -1 )
	{
	  ++ cnt_oth;
	  
	}
      else if( i >= 2 and i < SIZ(S)-1 and S[i] == 'C' )
	{
	  ++ cnt_C;
	  
	}
    }
  
  if( S[0] != 'A' or cnt_C != 1 or cnt_oth != SIZ(S)-2 )
    {
      printf("WA\n");
      
    }
  else
    {
      printf("AC\n");
      
    }
  

}


Measured memory_bytes: 256
#include <vector>
#include <iostream>
#include <cmath>
#include <map>
#include <algorithm>
#include <fstream>
#include <unistd.h>
#include <string>
#include <numeric>
#include <queue>
#include <deque>
#include <sstream>
#include <iomanip>
#include <set>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
typedef vector<P> vp;
typedef vector<PL> vpl;
typedef vector<vector<P>> vvp;
typedef vector<vector<PL>> vvpl;
const int INF = 1001001001;
const ll LINF = 1e18;
const double pi = 3.1415926535897932;
const string endstr = "\n";
#define FOR(i, a, b) for(ll i = (a); i < b; i++)
#define rep(i, n) for(ll i = 0; i < n; i++)
#define rrep(i, n) for(ll i = n; i >= 0; i--)
#define FORMAP(it, m) for(auto it = m.begin(); it != m.end(); it++)
#define ff first
#define ss second
#define pb push_back

template <typename T>
T gcd(T a, T b) {
    return (a == 0) ? b : gcd(b%a, a);
}
template <typename T>
T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}

bool p_comp_fs(const PL p1, const PL p2){ return p1.first < p2.first;};
bool p_comp_fg(const PL p1, const PL p2){ return p1.first > p2.first;};
bool p_comp_ss(const PL p1, const PL p2){ return p1.second < p2.second;};
bool p_comp_sg(const PL p1, const PL p2){ return p1.second > p2.second;};
template <typename T>
vector<T> uniquen(vector<T> vec){
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    return vec;
}


int main(){
    
    ll N, K; cin >> N >> K;
    vl A(N); rep(i, N) cin >> A[i];
    sort(A.rbegin(), A.rend());
    ll sum = accumulate(A.begin(), A.end(), 0ll);
    
    ll ans = 0;
    vb dp(K, false); dp[0] = true;
    rep(i, N){
        bool need = false;
        rep(j, K){
            need |= dp[j] && j+sum >= K;
        }
        if(!need) ans++;
        
        sum -= A[i];
        for(ll j = K-A[i]-1; j >= 0; j--){
            dp[j+A[i]] = dp[j+A[i]] || dp[j];
        }
    }
    cout << ans << endstr;
    return 0;
}


Measured memory_bytes: 256
#define ENABLE_DEBUG 1
// Kana's kitchen {{{
#include<bits/stdc++.h>
#define ALL(v) std::begin(v),std::end(v)
#define LOOP(k) for(i64 ngtkana_is_a_genius=0; ngtkana_is_a_genius<(i64)k; ngtkana_is_a_genius++)

using i32 = std::int_least32_t;
using i64 = std::int_least64_t;
using u32 = std::uint_least32_t;
using u64 = std::uint_least64_t;
using usize = std::size_t;

template <class T, class U> using pair = std::pair<U, T>;
template <class T> using diag_pair = std::pair<T, T>;
template <class... Args> using tuple = std::tuple<Args...>;
template <class T> using vec = std::vector<T>;
template <class T> using numr = std::numeric_limits<T>;

#ifdef NGTKANA
#include<debug.hpp>
#else
#define DEBUG(...)(void)0
#endif
/*}}}*/

struct flow_edge {
    usize to, rev;
    i64 cap, cost;

    flow_edge()=default;
    flow_edge(usize to_, usize rev_, i64 cap_, i64 cost_)
        : to(to_), rev(rev_), cap(cap_),  cost(cost_) {}
};

std::ostream& operator<< (std::ostream& os, flow_edge const& e) {
    return os << '(' << e.to << ';' << e.cap << '/' << e.cost << ')';
}

auto cmn = [](auto& x, auto y){ if (x>y) { x=y; return true; } return false; };

void err() {
    std::cout << -1 << '\n';
    exit(0);
}

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    std::cout << std::setprecision(15) << std::fixed;

    usize n, m;
    u32 F;
    std::cin >> n >> m >> F;
    vec<vec<flow_edge>> g(n);
    while (m--) {
        usize u, v, c, d;
        std::cin >> u >> v >> c >> d;
        usize su = g.at(u).size();
        usize sv = g.at(v).size();
        g.at(u).emplace_back(v, sv, c, d);
        g.at(v).emplace_back(u, su, 0, -d);
    }

    usize s = 0, t = n - 1;
    u32 inf = numr<u32>::max(), ans = 0;
    while (true) {
        vec<u32> dist(n, inf);
        dist.at(s) = 0;
        LOOP (n) {
            for (usize i=0; i<n; i++) {
                for (auto&& e: g.at(i)) if (e.cap!=0) {
                    cmn(dist.at(e.to), dist.at(i) + e.cost);
                }
            }
        }

        vec<usize> ckd(n), path = {t};
        auto dfs = [&](auto&& dfs_, usize x, i64 d) -> i64 {
            ckd.at(x) = true;
            if (x == t) return d;
            for (auto&& e: g.at(x)) if (e.cap!=0
                    && !ckd.at(e.to)
                    && dist.at(x) + e.cost == dist.at(e.to))
            {
                i64 f = dfs_(dfs_, e.to, std::min(d, e.cap));
                if (f) {
                    e.cap -= f;
                    g.at(e.to).at(e.rev).cap += f;
                    path.push_back(x);
                    return f;
                }
            }
            return 0;
        };

        i64 f = dfs(dfs, s, F);
        F -= f;
        ans += f * dist.at(t);
        if (F==0) break;
        if (F && f==0) err();

    }
    std::cout << ans << '\n';
}

/*
 * 次のことを F 回繰り返します。
 * s からベルマンフォードをして、各点への最短路長を計算です。
 * 答えに最短路長を足します。
 * 最短路を一つ選んで、それを反転させます。
 */



Measured memory_bytes: 3328
#include<iostream>
#include<string>
#include<map>
#include<cstdio>
#include<cctype>
using namespace std;
int main(){
  int n,cnt;
  string str;
  map<int,char> data;
  cin >> n;
  while(n--){
    cnt = 0;
    cin >> str;
    for(int i=0,l=str.size();i<l;i++){
      if(isalpha(str[i])) data[cnt] = str[i];
      else if(str[i]=='<') cnt--;
      else if(str[i]=='>') cnt++;
    }
    for(map<int,char>::iterator it = data.begin(),l = data.end();it!=l;it++){
      cout << (*it).second;
    }
    cout << endl;
    data.clear();
  }
}

Measured memory_bytes: 1200
a,b=map(int,input().split())

def xorsum(x):
  if x % 4 == 1:
    return 1
  elif x % 4 == 3:
    return 0
  elif x % 4 == 0:
    return x
  else:
    return 1 ^ x

print(xorsum(b)^xorsum(a-1))

Measured memory_bytes: 9116
#include <bits/stdc++.h>
using namespace std;
void update(int mat[3][3], int x) {
	for(int i = 0; i < 3; i++){
		for(int j = 0; j < 3; j++) {
			if(mat[i][j] == x) {
				mat[i][j] = -1;
				return;
			}
		}
	}
}

int main() {
	int a[3][3];
	int n, x;
	bool ans = false;
	for(int i = 0; i < 3; i++) for(int j = 0; j < 3; j++) cin >> a[i][j];
	cin >> n;
	while(n--) {
		cin >> x;
		update(a, x);
		if(!ans) {
			int cont = 0;
			for(int i = 0, j = 0; i < 3; i++, j++) cont += (a[i][j] == -1);
			if(cont == 3) ans = true;
			for(int i = 0; i < 3; i++) {
				cont = 0;
				for(int j = 0; j < 3; j++) {
					cont += (a[i][j] == -1);
				}
				if(cont == 3) {
					ans = true;
					i = 20;
				}
			}
			for(int j = 0; j < 3; j++) {
				cont = 0;
				for(int i = 0; i < 3; i++) {
					cont += (a[i][j] == -1);
				}
				if(cont == 3) {
					ans = true;
					j = 20;
				}
			}
			if(!ans) ans = (a[0][2] == a[1][1] && a[0][2] == a[2][0] && a[0][2] == -1);
		}
	}
	cout << (ans ? "Yes" : "No") << endl;
	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>

int q,a,b,c,d,s1[100005],s2[100005];
char s[100005],t[100005];

int Calc(int *S,int l,int r){return S[r]-S[l-1];}

int main()
{
    scanf("%s%s%d",s+1,t+1,&q);
    int sl=strlen(s+1),tl=strlen(t+1);
    for(int i=1;i<=sl;++i)s1[i]=s1[i-1]+(s[i]=='A');
    for(int i=1;i<=tl;++i)s2[i]=s2[i-1]+(t[i]=='A');
    while(q--)
    {
        scanf("%d%d%d%d",&a,&b,&c,&d);
        int c1=(b-a+1+Calc(s1,a,b))%3;
        int c2=(d-c+1+Calc(s2,c,d))%3;
        puts(c1==c2?"YES":"NO");
    }
    return 0;
}

Measured memory_bytes: 1408
N, Q = map(int, input().split())

w = [[] for _ in range(N+1)]
for _ in range(N-1):
    A, B = map(int, input().split())
    w[A].append(B)
    w[B].append(A)

cnt = [0]*(N+1)
for _ in range(Q):
    P, X = map(int, input().split())
    cnt[P] += X

flag = [False]*(N+1)

q = [1]
while q:
    n = q.pop()
    flag[n] = True
    for i in w[n]:
        if flag[i]:
            continue
        flag[i] = True
        cnt[i] += cnt[n]
        q.append(i)

print(" ".join([str(c) for c in cnt[1:]]))

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

using namespace std;
typedef long long ll;

#define rep(i, N) for (int i = 0; i < (int)N; i++)
const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,29)-1;


int main() {
  int N; cin >> N;
  int A[N], B[N]; rep(i,N) cin >> A[i];
  memcpy(B, A, sizeof(A));
  sort(B, B+N, greater<int>());
  rep(i,N) {
    int result = (A[i]==B[0]) ? B[1] : B[0];
    cout << result << endl;
  }
  return 0;
}

Measured memory_bytes: 3200
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 1; i < (int)(n); i++)
vector<int> input(int N) {
  vector<int> vec(N);
  for (int i = 0; i < N; i++) {
    cin >> vec.at(i);
  }
  return vec;
}

int main() {
  int n;
  cin >> n;
  vector<int> v=input(n);
  sort(v.begin(),v.end());
  reverse(v.begin(),v.end());
  
  int sum=0;
  rep(i,n){
    sum += v[i];
  }
  cout << sum+v[0]/2 << endl;
}


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

using namespace std;

const int MAXN = 1E5;
const int MAXA = 1E9;
int a[MAXN];
long long ans[MAXN + 1];

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    vector<pair<int, int>> important;
    int most = -1;
    for (int i = 0; i < n; i++)
    {
        if (a[i] > most)
        {
            most = a[i];
            important.push_back({i, most});
        }
    }
    sort(a, a + n);
    int ptr = n - 1;
    while (ptr >= 0)
    {
        int ind = important[(int) important.size() - 1].first;
        important.pop_back();
        int target = important.empty() ? 0 : important[(int) important.size() - 1].second;
        while (ptr >= 0 && a[ptr] > target)
        {
            int start = ptr;
            while (ptr - 1 >= 0 && a[ptr - 1] == a[start])
                ptr--;
            int next = ptr - 1 >= 0 ? a[ptr - 1] : 0;
            ans[ind] += (long long) (n - ptr) * (a[start] - next);
            ptr--;
        }
    }
    for (int i = 0; i < n; i++)
        cout << ans[i] << endl;
    return 0;
}


Measured memory_bytes: 3188