akhauriyash/Code-Regression huggingface dataset:
from math import factorial
n=int(input())

def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(int(n))
  return table

s=[]

for i in range(1,n+1):
  s=s+(prime_decomposition(i))

count2=0
count4=0
sumation=0
for i in range(1,n+1):
  if s.count(i)==2 or s.count(i)==3:
    count2 +=1
  elif s.count(i) >3:
    count4 +=1

sumation += count4*(count4-1)/2*(count2+count4-2)

count2=0
count4=0
for i in range(1,n+1):
  if s.count(i)>=24:
    count2 +=1
  elif s.count(i) >=2:
    count4 +=1
    
sumation += count2*(count2+count4-1)

count2=0
count4=0
for i in range(1,n+1):
  if s.count(i)>=14:
    count2 +=1
  elif s.count(i) >=4:
    count4 +=1
    
sumation += count2*(count2+count4-1)

count2=0
count4=0
for i in range(1,n+1):
  if s.count(i)>=74:
    count2 +=1
    
sumation += count2

print(int(sumation))

Measured memory_bytes: 38256
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <fstream>
using namespace std;
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toStr(T x) { ostringstream sout; sout << x; return sout.str(); }
typedef vector<int> vi;
typedef vector<vi>  vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i,0,(n)-1)
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = INT_MAX / 10;
const int MOD = 1000000007;

struct UnionFind {
	vi data;
	UnionFind(int size) : data(size, -1) {}
	bool unite(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool find(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};

int main() {
	int f[1001];
	f[0] = 1, f[1] = 2;
	FOR(i, 2, 1000) {
		f[i] = (f[i - 1] + f[i - 2])%1001;
	}

	int V, d;
	while (cin >> V >> d) {
		UnionFind uf(V+1);
		FOR(i, 1, V) {
			FOR(j, i + 1, V) {
				if (abs(f[i] - f[j]) < d) {
					uf.unite(i, j);
				}
			}
		}
		
		set<int> ans;
		FOR(i, 1, V) {
			ans.insert(uf.root(i));
		}
		cout << ans.size() << endl;
	}
	return 0;
}

Measured memory_bytes: 3112
#include<algorithm>
#include<climits>
#include<cmath>
#include<cstdlib>
#include<iomanip>
#include<iostream>
#include<numeric>
#include<string>
using namespace std;

long gcd(long x, long y) { if (x > y) { return gcd(y, x); } long r; while (y != 0) { r = x % y; x = y; y = r; }return x; }
long lcm(long x, long y) { return(x / gcd(x, y)) * y; }
void indexsort(long* first, long* last, long* func) { sort(first, last, [&](long a, long b) {return func[a] < func[b]; }); }
//--------------------

int main() {

	long N; cin >> N;
	long res = INT_MAX;
	long a[200009] = {}; for (int i = 0; i < N; i++) cin >> a[i];
    
	long sum[200009] = {}; sum[0] = a[0]; for (int i = 1; i < N; i++) sum[i] = sum[i - 1] + a[i];
	for (int i = 0; i < N - 1; i++) res = min(res, abs((sum[N - 1] - sum[i]) - sum[i]));
	
    cout << res << endl;
}

Measured memory_bytes: 3328
def main():
    a, b, n = map(int, input().split())

    x = (n - (b - 2) + (b - 1)) // b
    y = max(0, b * x - 1)
    ans = max((a * y) // b - a * (y // b), (a * n) // b - a * (n // b))

    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 9184
#! -*- coding:utf-8 -*-

import sys

n = 0
a_score = 0
b_score = 0
results = []
init = 1
for line in sys.stdin:
    line = line.rstrip()
    sp_line = map(int, line.split(" "))
    if len(sp_line) == 1:
        if init:
            init = 0
        else:
            results.append((a_score, b_score))
            a_score = 0
            b_score = 0
        if sp_line[0] == 0:
            for a,b in results:
                print "%s %s" % (a, b)

    else:
        a, b = sp_line
        if a > b:
            a_score += a+b
        if b > a:
            b_score += a+b
        if a == b:
            a_score += a
            b_score += b

Measured memory_bytes: 4260
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cassert>
#include <cstdarg>
#include <sys/time.h>
#include <fstream>
//#include "cout.h"

using namespace std;

#define SZ(x) ((int)x.size())
#define MSET(x,a) memset(x, a, (int)sizeof(x))
#define PB push_back
#define VI vector < int >
#define PII pair < int, int >
#define LL long long
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(), (v).end()
#define FIT(it,v) for (__typeof((v).begin()) it = (v).begin(); it != (v).end(); it++)
#define OUT(A) cout << #A << " = "<< (A) << endl
#define OUT2(A, B) cout << "(" << #A << ", " << #B << ") = (" << (A) << ", "<< (B) << ")" << endl
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }

#define present(c, e) ((c).find((e)) != (c).end())
#define cpresent(c, e) (find(ALL(c), (e)) != (c).end())



void init() {

}

void input() {

}

void solve() {
  int n, k;
  cin >> n >> k;
  int cnt = 0;
  for(int i = 1 ; i <= n ; i+=2) {
    cnt++;
    if(cnt == k) {
      cout << "YES" << endl;
      return;
    }
  }
  cout << "NO" << endl;
}

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


Measured memory_bytes: 256
import java.io.InputStream;
import java.math.*;
import java.math.BigInteger;
import java.util.Scanner;
import java. util. Arrays;

public class Main {

    public static void main(String[] args) {
        long n,m,j,k,p,q,o,l,s,tt=1;
        int i;
        char ch;
        BigInteger an,su,u,v;
        String a,b,c;
        Scanner sc= new Scanner(System.in);
        b=sc.nextLine();
        n=Long.parseLong(b);
        a=sc.nextLine();
        k=0;
        for(i=0;i<n;)
        {
            k++;
           while(i+1<n && a.charAt(i)==a.charAt(i+1))
           {
              i++;
           }
           i++;
        }
        System.out.println(k);




    }
}


Measured memory_bytes: 40516
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<string>
#include<math.h>
#include<stdlib.h>
#include<time.h>
#include<map>
#include<queue>
#include<set>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
int n;
long long t,ans;
long long gcd(long long a,long long b){
	if (!b) return a;else return gcd(b,a%b);
}
int main(){
	scanf("%d",&n);
	ans=1;
	fo(i,1,n){
		scanf("%lld",&t);
		ans=ans/gcd(ans,t)*t;
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 128
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <unordered_map>
#include <map>
#define rep(i,n) for (int i=0; i<n;++i)
#define rep_down(i,n) for (int i=n-1; i>=0;--i)
typedef long long ll;
using namespace std;
const int INF = 1000000007;
string S;
unordered_map<char, int> M;

bool check(string s, char c) {
  bool is_end = true;
  for (auto x : s) if (x != c) is_end = false;
  return is_end;
}

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

  cin >> S;
  rep(i, S.size()){
    M[S[i]] += 1;
  }

  int ans = INF;

  for (auto it=M.begin(); it !=M.end(); ++it){
    char c = it -> first;
    string T = S;
    rep(i, S.size()){
      if (check(T, c)) {
        ans = min(i, ans);
        break;
      }
      string _t = "";
      rep(j, T.size()-1){
        if (T[j] == c || T[j + 1] == c) _t += c;
        else _t += T[j];
      }
      T = _t;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<math.h>
#include<iomanip>
#include<stdio.h>
using namespace std;

int main(){

  long long int ans, n, m;
  cin >> n >> m;

  ans = 1900*m*pow(2, m) + 100*(n-m)*pow(2, m);

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#define mp(x,y) make_pair(x,y)
using namespace std;
typedef pair<int,int> pi;
const int N=100005;
int n,f[N];
set<int>se[N];
map<pi,int>ma;
queue<pi>que;
inline int read(){
	int x=0,f=0,c=getchar();
	for(;c>'9'||c<'0';f=c=='-',c=getchar());
	for(;c>='0'&&c<='9';c=getchar())
	x=(x<<1)+(x<<3)+c-'0';return f?-x:x;
}
inline int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
int main(){
    int i,x,y;
    n=read();
    for(i=1;i<=n+n-2;i++){
        x=read();y=read();
        se[x].insert(y);se[y].insert(x);
        ma[mp(x,y)]++;ma[mp(y,x)]++;
        if(ma[mp(x,y)]==2)que.push(mp(x,y));
    }
    for(i=1;i<=n;i++)f[i]=i;
    set<int>::iterator it;
    while(!que.empty()){
        x=que.front().first;y=que.front().second;
		que.pop();x=find(x);y=find(y);
        se[x].erase(y);se[y].erase(x);
        if (se[x].size()<se[y].size())swap(x,y);
        for (it=se[y].begin();it!=se[y].end();it++){
            int to=(*it);
            ma[mp(to,y)]=ma[mp(y,to)]=0;
            se[to].erase(y);se[to].insert(x);
            ma[mp(to,x)]++;ma[mp(x,to)]++;
            if(ma[mp(to,x)]==2)que.push(mp(to,x));
            se[x].insert(to);
        }f[y]=x;se[y].clear();
    }
    int s=0;
    for(i=1;i<=n;i++)s+=f[i]==i;
    puts(s==1?"YES":"NO");
    return 0;
}

Measured memory_bytes: 57728
n=int(input())

x=list(input())
l=len(x)

for k in range(n-1):
    a=list(input())
    m=len(a)
    for i in range(l-1,-1,-1):
        for j in range(m-1,-1,-1):
            if x[i]==a[j]:
                del a[j]
                m-=1
                break
        else:
            del x[i]
            l-=1

x.sort()
   
print(''.join(x))


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

const int MAX = 200000;

int64_t getAbs(int b, int *A, int N) {
	int64_t ans = 0;
	for (int i = 0;i < N;i ++) ans += abs(A[i] - b);
	return ans;
}
int main() {
	int N;
	static int A[MAX];
	cin >> N;
	for (int i = 0;i < N;i ++) {
		cin >> A[i];
		A[i] -= i + 1;
	}
	
	int64_t l = -1000000000, ml, mr, r = 1000000000;
	while(r - l > 2) {
		ml = l + (r - l) / 3;
		mr = l + (r - l) * 2 / 3;
/*		cout << "(" << l << "," << getAbs(l, A, N) << "), (" << ml << "," << getAbs(ml, A, N) << "), (" << 
		mr << "," << getAbs(mr, A, N) << "), (" << r << "," << getAbs(r, A, N) << ")" << endl;*/
		if (getAbs(ml, A, N) <= getAbs(mr, A, N) && getAbs(mr, A, N) <= getAbs(r, A, N)) { // 答えはlからmrの間
			r = mr;
		} else { // 答えはmlからrの間
			l = ml;
		}
	}
	cout << min(min(min(getAbs(l, A, N), getAbs(ml, A, N)), getAbs(mr, A, N)), getAbs(r, A, N));
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり

まずiは定数なので前もってA_iから引いておけば影響しない
この時、bの値はどうなるか考えてみると、これは二次関数になる
ので、三分探索すると答えが求まる
*/

Measured memory_bytes: 1024
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#include <iomanip>
#include <complex>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
typedef pair<pii,int> ppiii ;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
typedef complex<double> P;
long long int MOD=1000000007;
#define SIZE 200005

int main(){
	int n;
	cin>>n;
	vector<ll> a(n);
	ll sum=0;
	for(int i=0;i<n;i++){
		cin>>a[i];
		sum+=a[i];
	}
	sum=sum/(ll)n;
	ll ans=0;
	for(int i=0;i<n;i++){
		ans+=(a[i]-sum)*(a[i]-sum);
	}
	ll temp=0;
	for(int i=0;i<n;i++){
		temp+=(a[i]-sum-1)*(a[i]-sum-1);
	}
	ans=min(ans,temp);
	temp=0;
	for(int i=0;i<n;i++){
		temp+=(a[i]-sum+1)*(a[i]-sum+1);
	}
	ans=min(ans,temp);
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n,k,arr[55],dp[55][55],sum;
int solve(int index, int count){
	if(count > k) return INT_MIN;
	if(index == n || count == k) return 0;
	if(dp[index][count] != -1) return dp[index][count];
	return dp[index][count] = max(arr[index]+solve(index+1,count+1),solve(index+1,count));
}
int main(){
	cin>>n>>k;
	for(int i=0; i<n; i++) cin>>arr[i];
	memset(dp, -1, sizeof dp);
	cout<<solve(0,0)<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef pair<int, int> P;
typedef long long ll;
int main(){
    string s1,s2,s3;
    cin >> s1 >> s2 >> s3;
    cout << (char)(s1[0]-'a'+'A') << (char)(s2[0]-'a'+'A') << (char)(s3[0]-'a'+'A')<<endl;
    return 0;
}

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

using namespace std;
using ll = long long;

#define REP(i, n) for (ll i = 0; i < n; i++)
#define INF 9223372036854775807
#define all(x) (x).begin(), (x).end()

ll ts = 1000000007;

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

  ll a, b;
  cin >> a >> b;

  cout << max(a + b, max(2 * a - 1, 2 * b - 1)) << "\n";
}

Measured memory_bytes: 256
#include <algorithm>
#include <complex>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <vector>

using std::cin;
using std::cout;
using std::endl;

using std::string;
using std::to_string;
using std::vector;
using std::set;
using std::queue;
using std::priority_queue;

using std::min;
using std::max;
using std::sort;
using std::abs;

bool solve(const vector<int>& a, int k) {
    const int BIAS = 8000;
    int n = a.size();

    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += a[i];
    }
    if (abs(k) > sum) {
        return false;
    }

    vector<vector<bool>> dp(n + 1,
                            vector<bool>(BIAS + BIAS + 1));  // bias 8000!!

    dp[0][0 + BIAS] = true;

    for (int i = 1; i <= n; i++) {
        for (int j = -BIAS; j <= BIAS; j++) {
            dp[i][j + BIAS] = false;

            int ind;
            ind = j + a[i - 1];
            if (-BIAS <= ind && ind <= BIAS && dp[i - 1][ind + BIAS]) {
                dp[i][j + BIAS] = true;
            }

            ind = j - a[i - 1];
            if (-BIAS <= ind && ind <= BIAS && dp[i - 1][ind + BIAS]) {
                dp[i][j + BIAS] = true;
            }
        }
    }

    return dp[n][k + BIAS];
}

int main(void) {
    string s;
    cin >> s;
    const int slen = s.length();

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

    int fcnt = 0;
    for (int i = 0; i < slen && s[i] == 'F'; i++) {
        fcnt++;
    }

    const int init_x = fcnt;
    const int init_y = 0;

    const int diff_x = x - init_x;
    const int diff_y = y - init_y;

    vector<int> xs;
    vector<int> ys;
    int cnt;
    int phase = 1;  // 1 : x, -1 : y
    for (int i = fcnt; i < slen; i += cnt) {
        if (s[i] == 'T') {
            phase *= -1;
            cnt = 1;
            continue;
        }

        cnt = 0;
        for (int j = i; j < slen && s[j] == 'F'; j++) {
            cnt++;
        }

        if (phase == 1) {
            xs.push_back(cnt);
        } else {
            ys.push_back(cnt);
        }
    }

    /*
    for(int i : xs){
        cout << i << " ";
    }
    cout << endl;
    for(int i : ys){
        cout << i << " ";
    }
    cout << endl;
    */

    bool ans = solve(xs, diff_x) && solve(ys, diff_y);
    cout << (ans ? "Yes" : "No") << endl;

    return 0;
}



Measured memory_bytes: 5632
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		int k = s.nextInt();
		
		int a[] = new int[n];
		for(int i=0;i<n;i++)
			a[i] = s.nextInt();
		
		Arrays.parallelSort(a);
		int sum = 0;
		for(int i=0;i<k;i++)
			sum+=a[i];
		System.out.println(sum);
	}

}


Measured memory_bytes: 38752
#include <iostream>
#include <cstdio>
#define N 2005
using namespace std;

int n, w[N], b[N], d[N][N], dw[2 * N][N], db[2 * N][N];
char c;
int main()
{
	int i, j, t, t1, t2;
	cin >> n;
	for (i = 1; i <= 2 * n; i++) {
		scanf("%s %d", &c, &t);
		if (c == 'W') w[t] = i;
		else b[t] = i;
		for (j = 1; j <= n; j++) {
			dw[i][j] = dw[i - 1][j], db[i][j] = db[i - 1][j];
			if (c == 'W') dw[i][j] += (t >= j);
			else db[i][j] += (t >= j);
		}
	}
	for (i = 0; i <= n; i++) {
		for (j = 0; j <= n; j++) {
			t1 = i > 0 ? d[i - 1][j] + dw[w[i]][i + 1] + db[w[i]][j + 1] : 1e9;
			t2 = j > 0 ? d[i][j - 1] + dw[b[j]][i + 1] + db[b[j]][j + 1] : 1e9;
			d[i][j] = min(t1, t2);
			d[0][0] = 0;
		}
	}
	cout << d[n][n];
    return 0;
}

Measured memory_bytes: 78720
#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 fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------

//左端をクリックかF9でブレークポイントを付ける
//( 条件式 ? Trueの処理:Falseの処理 )

void _main() {
	int N[5];
	int sum = 0;
	int sumFinal = 10;
	for (int i = 0; i < 5; i++) {
		cin >> N[i];
		if (N[i] % 10 != 0) {
			sum += N[i] / 10 * 10+10;
			//余りがある数の中で、1の位がもっとも大きいものを最後にする。
			if (N[i] % 10 < sumFinal) {
				sumFinal = N[i] % 10;
			}
		}
		else {
			sum += N[i];
		}
	}
	cout << sum + sumFinal - 10 << endl;//-10は最後の物を余計に作ってしまった分
}

Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <iostream>
#include <vector>
#include <cstdlib>
#include <cstring>
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;

char map[1005][1005];
int dis[1005][1005];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int row,col,n;
int current = 1;
int firstX,firstY;
int ans = 0;
typedef pair<int,int> pos;
queue <pos> q;

void bfs(){
    while(q.size()){
        pos t = q.front();
        q.pop();
        if(map[t.first][t.second] - '0'== current){
            ans += dis[t.first][t.second];
            current++;
            //清空队列保证下次起点正常
            while(q.size()){
                q.pop();
            }
            //重置距离数组
            memset(dis,INF,sizeof dis);
            dis[t.first][t.second] = 0;
            //设置下一次广搜的起点
            q.push(pos(t.first,t.second));
        }
        //四个方向进行bfs
        for(int i = 0;i<4;i++){
            int x = t.first + dx[i];
            int y = t.second + dy[i];
            if(x<0 || x>= row || y < 0|| y>=col || map[x][y] == 'X' || dis[x][y] != INF)//INF判断是否走过
                continue;
            else{
                q.push(pos(x,y));
                dis[x][y] = dis[t.first][t.second] + 1;
            }
        }
    }
}

int main(){
    cin>>row>>col>>n;
    //初始化
    ans = 0;
    memset(dis,INF,sizeof dis);
    for(int i = 0;i<row;i++){
        for(int j = 0;j<col;j++){
            cin>>map[i][j];
            if(map[i][j] == 'S'){
                //设置起点
                q.push(pos(i,j));
                dis[i][j] = 0;
            }
        }
    }
    //开始广搜
    bfs();
    cout<<ans<<endl;
    return 0;
}


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

int main() {
  int n,k;
  cin >> n >> k;
  vector<int> a(n);
  for(int i=0;i<n;i++){
    cin >> a.at(i);
  }
  for(int i=0;i<k;i++){
    vector<int> b(n+1);
    for(int j=0;j<n;j++){
      int l=max(0,j-a.at(j));
      int r=min(n,j+a.at(j)+1);
      b.at(l)++;
      b.at(r)--;
    }
    for(int j=0;j<n;j++){
      b.at(j+1)+=b.at(j);
    }
    b.pop_back();
    if(a==b){
      break;
    }
    a=b;
  }
  for(int i=0;i<n;i++){
    cout << a.at(i) << endl;
  }
}


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

int main(void) {
	char s[301], t[101];
	scanf("%s", s);
	scanf("%s", t);
	int len = strlen(s);
	for (int i = 0; i < len; i++) {
		if (s[i] == t[0]) {
			for (int j = 0; j < len; j++) {
				if (s[(i+j)%len] != t[j]) {
					break;
				}
				else {
					if (j == len - 1) {
						printf("Yes\n");
						return 0;
					}
				}
			}
		}
	}
	printf("No\n");
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <math.h>
#include <utility>
#include <algorithm>
#include <functional>
#include <vector>
#include <numeric>
#include <bits/stdc++.h>

#define int long long

struct edge {
    int to;
    int cost;
};

using namespace std;
using vi = vector<int>;
using vii = vector<vector<int>>;
using vb = vector<bool>;
using qi = queue<int>;
using P = pair<int, int>;
// using graph = vector<vector<edge>>;
using graph = vector<vector<int>>;

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

const int inf = 1LL << 60;
// const int inf = 100000000;
const int mod = 1000000007;

const int maxn = 100;
int x, k, d;

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

    cin >> x >> k >> d;

    int n = abs(x)/d;
    if (n >= k) {
        x = abs(x) - d*k;
    } else {
        x = abs(x) - d*n;
        if ((k-n)%2 != 0) x = d - abs(x);
    }

    cout << x << "\n";
}


Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
#define REP(i,b,e) for(int i=(b);i<(e);++i)
#define RREP(i,b,e) for(int i=(b)-1;i>=e;--i)
#define rep(i,e) for(int i=0;i<(e);++i)

constexpr int MOD = 1000000007;
constexpr int INF = 1LL << 30;
constexpr long long LLINF = 1LL << 62;
constexpr double EPS = 1e-9;

struct Initializer {
  Initializer() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(15) << boolalpha;
  }
} initializer;

template<typename T>
istream &operator>>(istream &is, vector<T> &vec) {
  for (T &x : vec) is >> x;
  return is;
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  os << "[";
  for (auto it = vec.begin(); it != vec.end(); ++it) {
    if (it != vec.begin()) os << ", ";
    os << *it;
  }
  return os << "]";
}

template<typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &pa) {
  return os << "(" << pa.first << ", " << pa.second << ")";
}

template<typename Tuple, size_t N>
struct TuplePrinter {
  static void print(const Tuple &t) {
    TuplePrinter<Tuple, N-1>::print(t);
    cout << ", " << get<N-1>(t);
  }
};

template<typename Tuple>
struct TuplePrinter<Tuple, 1> {
  static void print(const Tuple &t) {
    cout << get<0>(t);
  }
};

template<typename... T>
ostream &operator<<(ostream &os, const tuple<T...> &tup) {
  os << "(";
  TuplePrinter<decltype(tup), sizeof...(T)>::print(tup);
  return os << ")";
}

template<typename T>
ostream &operator<<(ostream &os, const set<T> &se) {
  os << "{";
  for (auto it = se.begin(); it != se.end(); ++it) {
    if (it != se.begin()) os << ", ";
    os << *it;
  }
  return os << "}";
}

template<typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &ma) {
  os << "{";
  for (auto it = ma.begin(); it != ma.end(); ++it) {
    if (it != ma.begin()) os << ", ";
    os << it->first << ": " << it->second;
  }
  return os << "}";
}

inline void print(void) { cout<<'\n'; }
template<class T> inline void print(const T &x) { cout<<x<<'\n'; }
template<class T, class... U> inline void print(const T &x, const U&... y) { cout<<x<<" "; print(y...); }
#define dump(...) cout<<#__VA_ARGS__<<": [L_"<<__LINE__<<"]"<<'\n'; print(__VA_ARGS__);cout<<'\n';

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


int main() {
  int n; cin>>n;
  vector<long long> a(3*n);
  rep(i, 3*n) cin>>a[i];
  sort(a.begin(), a.end(), greater<long long>());
  long long ans = 0;
  for (int i = 1, cnt = 0; cnt < n; i+=2){
    ans += a[i];
    ++cnt;
  }
  print(ans);

  return 0;
}

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

#define CO const
#define IN inline
typedef long long int64;

template<class T> IN T read(){
	T x=0,w=1;char c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-') w=-w;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0';
	return x*w;
}
template<class T> IN T read(T&x){
	return x=read<T>();
}

CO int N=2e5+10;
struct node {int a,b;} p[N];
map<int,int> now,nxt;

IN int64 calc(CO node&p,int t){
	return (int64)p.a*t+p.b;
}
int main(){
	int n=read<int>(),T=read<int>();
	for(int i=1;i<=n;++i) read(p[i].a),read(p[i].b);
	sort(p+1,p+n+1,[&](CO node&p,CO node&q)->bool{
		return (int64)(p.b+1)*q.a<(int64)(q.b+1)*p.a;
	});
	now[0]=0;
	int k=n+1;
	for(int i=1;i<=n;++i){
		if(p[i].a==0) {k=i; break;}
		nxt=now;
		for(CO pair<int,int>&j:now){
			int c=j.first,t=j.second;
			if(t+1+calc(p[i],t+1)<=T){
				t=t+1+calc(p[i],t+1);
				if(!nxt.count(c+1)) nxt[c+1]=t;
				else nxt[c+1]=min(nxt[c+1],t);
			}
		}
		now=nxt;
	}
	sort(p+k,p+n+1,[&](CO node&p,CO node&q)->bool{
		return p.b<q.b;
	});
	int ans=0;
	for(CO pair<int,int>&j:now){
		int c=j.first,t=j.second;
		for(int i=k;i<=n;++i)
			if(t+1+calc(p[i],t+1)<=T)
				++c,t=t+1+calc(p[i],t+1);
		ans=max(ans,c);
	}
	printf("%d\n",ans);
	return 0;
}


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

typedef pair<long long, long long> P;
typedef pair<P, string> PP;

void solve(int n, int q){
	vector<PP> v;
	for(int i=0; i<n; ++i){
		string s;
		int a, b;
		cin >> s >> a >> b;
		v.push_back(PP(P(b-a+1, b), s));
	}
	sort(v.begin(), v.end());
	for(int i=0; i<q; ++i){
		int a;
		cin >> a;
		for(int j=0; j<v.size(); ++j){
			if(j == 0 && a < v[j].first.first){
				cout << "Unknown\n";
				break;
			}
			if(v[j].first.first <= a && a <= v[j].first.second){
				cout << v[j].second << " " << a-v[j].first.first+1 << "\n";
				break;
			}else if(v[j].first.second < a && (j==v.size()-1 || a < v[j+1].first.first)){
				cout << "Unknown\n";
				break;
			}
		}
	}
}

int main(){
//	cin.tie(0);
//	ios::sync_with_stdio(false);
	while(1){
		int n, q;
		cin >> n >> q;
		if(n == 0 && q == 0) return 0;
		solve(n, q);
	}
}


Measured memory_bytes: 3196
#include <bits/stdc++.h>
#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 sp(n) cout << fixed << setprecision(n)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
using namespace std;
int main(void){
    string s;cin>>s;
    rep(i,s.size())s[i]='x';
    cout<<s<<endl;
}

Measured memory_bytes: 3600
n = int(input())
odd_list = [num for num in range(1, n+1, 2)]
cnt_8 = 0
for i in odd_list:
    cnt = 0
    for j in range(1, i+1, 2):
        if i % j == 0:
            cnt += 1
    if cnt == 8:
        cnt_8 += 1
print(cnt_8)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}
#ifdef __LOCAL
#define debug(x) cerr << __LINE__ << ": " << #x << " = " << x << endl
#define debugArray(x, n)                                      \
  cerr << __LINE__ << ": " << #x << " = {";                   \
  for (long long hoge = 0; (hoge) < (long long)(n); ++(hoge)) \
    cerr << ((hoge) ? "," : "") << x[hoge];                   \
  cerr << "}" << endl
#else
#define debug(x) (void(0))
#define debugArray(x, n) (void(0))
#endif

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N, M;
  cin >> N >> M;
  vector<vector<int>> graph(N);
  for (int i = 0; i < M; i++) {
    int A, B;
    cin >> A >> B;
    graph[--A].push_back(--B);
  }
  int used[N];
  fill(used, used + N, 0);
  deque<int> cycle;
  int ts = 2;
  function<bool(int)> dfs = [&](int v) {
    if (used[v] == ts) return true;
    if (used[v]) return false;
    used[v] = ts;
    for (int u : graph[v]) {
      if (dfs(u)) {
        cycle.push_back(v);
        return true;
      }
    }
    used[v] = ts - 1;
    return false;
  };
  for (int i = 0; i < N; i++) {
    if (used[i]) continue;
    if (dfs(i)) break;
    ts++;
  }
  if (cycle.size() == 0) {
    cout << -1 << '\n';
    return 0;
  }
  //   debugArray(cycle, cycle.size());
  int n = cycle.size();
  for (bool upd = true; upd;) {
    auto check = [&]() {
      n = cycle.size();
      for (int i = 0; i < n; i++) {
        int v = cycle.front();
        cycle.pop_front();
        for (int u : graph[v]) {
          for (int j = 0; j < n - 2; j++) {
            if (u == cycle[j]) {
              for (int k = n - 2; k > j; k--) cycle.pop_back();
              cycle.push_back(v);
              return true;
            }
          }
        }
        cycle.push_back(v);
      }
      return false;
    };
    upd = check();
  }
  cout << n << '\n';
  for (int i = 0; i < n; i++) cout << cycle[i] + 1 << '\n';
  return 0;
}


Measured memory_bytes: 3776
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    int m;
    cin>>m;
    int sum = 0;
    for(int i=0;i<m;++i){
        int val;
        cin>>val;
        sum += val;
    }
    if(sum<=n){
        cout<<n-sum<<'\n';
    }
    else{
        cout<<-1<<'\n';
    }
    return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順

int main() {
    int X; cin >> X;
    if (X >= 30) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 3632
N, M, X, Y = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
Z = [z for z in range(-100, 101) if (X < z <= Y) and (max(x) < z <= min(y))]
if len(Z) is not 0: print('No War')
else: print('War')

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

int main(){
	string X;
	cin >> X;
	int l = 0;
	int ans = 0;
	for( auto c : X ){
		if( c == 'S' ) l++;
		else if( c == 'T' ) {
			if(l) l--;
			else ans++;
		}
	}
	cout << ans + l << endl;
}

Measured memory_bytes: 640
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        a: usize,
        b: usize,
        c: usize,
    }

    if a > b + c {
        println!("{}", 0);
    } else {
        println!("{}", b + c - a);
    }
}


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

int main(){
  string s, t;
  cin >> s >> t;
  for(int i=0; i<t.length(); i++){
    if(s==t){
      cout << "Yes";
      return 0;
    }
    char tmp=t[0];
    for(int j=1; j<t.length(); j++)t[j-1]=t[j];
    t[t.length()-1]=tmp;
  }
  cout << "No";
  return 0;
}
      

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

#define int long long
#define endl "\n"
#define REP(i,a,n) for(int i=a;i<n;++i)
#define REPR(i,a,n) for(int i=a;i>n;--i)
#define RUP(a,b) ((a+b-1)/(b))
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define MOD 1000000007
#define INF LLONG_MAX/2

typedef long long ll;
typedef pair<int,int> Pii;
typedef tuple<int,int,int> Tiii;
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef vector<Pii> VPii;
typedef vector<string> Vs;

template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T> void YesNo(T a) {cout<<(a?"Yes":"No")<<endl;}
template<class T> void YESNO(T a) {cout<<(a?"YES":"NO")<<endl;}
void vin(Vi &v){REP(i,0,(v).size()) cin>>v[i];}
void vin(Vi &v,Vi &v2){REP(i,0,(v).size()) cin>>v[i]>>v2[i];}
void vout(Vi &v){for(int i=0;i<(v).size();i++) cout<<v[i]<<" ";cout<<endl;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
void uniq(Vi &v){sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());}
int ctoi(char c){if(c>='0'&&c<='9'){return c-'0';}return 0;}
void accum(Vi &v){REP(i,1,(v).size()) v[i]+=v[i-1];}
bool comp(Pii a,Pii b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}

signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
    string s;
    cin>>s;
    int n=s.size();
    Vi a;
    int now=0;

    if(s[0]=='>') a.pb(0);
    REP(i,0,n){
        if(i==0){
            if(s[i]=='<') now++;
            else now--;
        }else{
            if(now>0 && s[i]=='>'){
                a.pb(now);
                now=-1;
            }else if(now>0 && s[i]=='<'){
                now++;
            }else if(now<0 && s[i]=='>'){
                now--;
            }else if(now<0 && s[i]=='<'){
                a.pb(now);
                now=1;
            }
        }
        if(i==n-1) a.pb(now);
    }
    if(s[n-1]=='<') a.pb(0);
//    vout(a);

    int ans=0;
    REP(i,0,a.size()/2){
        int ma=max(a[2*i],-a[2*i+1]);
        int mi=min(a[2*i],-a[2*i+1]);
        ans += ma*(ma+1)/2;
        ans += mi*(mi-1)/2;
    }
    cout<<ans<<endl;
    return 0;
}


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

#define pb push_back
#define st first
#define nd second
#define lb lower_bound
#define ub upper_bound

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

ll N,W,v[105],w[105],dp[105][100005];

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin>>N>>W;
    for(int i=1;i<=N;++i) {
        cin>>w[i]>>v[i];
    }
    for(int i=1;i<=N;++i) {
        for(int j=1;j<=W;++j) {
            if(w[i]<=j) dp[i][j]=max(dp[i-1][j],v[i]+dp[i-1][j-w[i]]);
            else dp[i][j]=dp[i-1][j];
        }
    }
    cout<<dp[N][W];
    return 0;
}


Measured memory_bytes: 79488
# coding: utf-8
# Your code here!

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

Y = Y//1000

flag = 0

for i in range(N+1):
    NN = N-i
    YY = Y - i
    for j in range(NN+1):
        NNN = NN - j
        YYY = YY - 5*j
#        if i == 0 and j == 0:
#            print(NNN,YYY)
        if 10*NNN == YYY:
            flag = 1
            cc = i
            bb = j
            aa = NNN
            
        

if flag == 0:
    aa=-1
    bb=-1
    cc=-1
print(aa,bb,cc)



Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
long long a,b,c,x;
int main()
{
    cin>>a>>b>>c;
    x=a-c;
    c=c-a;
    a=max(x,(long long)0);
    b=b-max((long long)0,c);
    b=max((long long)0,b);
    cout<<a<<" "<<b;
    return 0;
}
/*#include <bits/stdc++.h>
using namespace std;
int main()
{
    cin>>n>>m;
    for(i=1;i<=n;i++)
        cin>>v[i];
    sort(v+1,v+n+1);
    for(i=1;i<=n;i++)
        s[i]=s[i-1]+v[i];
    i=n;
    while(true)
    {
        sum=sum+s[i]
    }
    return 0;
}
*/


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <string>
#include <queue>
#include <cmath>
#include <numeric>
#include <list>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <climits>
#include <memory.h>
#include <memory>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <map>
#define _USE_MATH_DEFINES
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, P> PP;
typedef vector<int> vec;
typedef vector<vec> mat;
const int INF = 1 << 30;
const double EPS = 1e-9;

int n, m;
int V;
char area[100][100];
bool can[100][100];
bool used[10000];
int match[10000];
vector<int> G[10000];
int dy[] = {
	0, 0, 1, 1
};
int dx[] = {
	1, -1, 1, -1
};

bool dfs(int v){
	used[v] = true;
	for(int i = 0; i < (int)G[v].size(); i++){
		int u = G[v][i], w = match[u];
		if(w < 0 || !used[w] && dfs(w)){
			match[v] = u;
			match[u] = v;
			return true;
		}
	}
	return false;
}

int matching(){
	int res = 0;
	memset(match, -1, sizeof(match));
	for(int v = 0; v < V; v++){
		if(match[v] < 0){
			memset(used, false, sizeof(used));
			if(dfs(v)){
				res++;
			}
		}
	}
	return res;
}

void add_edge(int from, int to){
	G[to].push_back(from);
	G[from].push_back(to);
}

int gcd(int u, int v){
	int t;
	while(u > 0){
		if(u < v){
			t = u;
			u = v;
			v = t;
		}
		u %= v;
	}
	return v;
}

int b[1000];
int r[1000];

int main(){
	int m, n;
	while(cin >> m >> n && (m || n)){
		for(int i = 0; i < m; i++){
			cin >> b[i];	
		}
		for(int i = 0; i < n; i++){
			cin >> r[i];
		}	
		for(int i = 0; i < m; i++){
			for(int j = 0; j < n; j++){
				if(gcd(b[i], r[j]) > 1){
					add_edge(i, m + j);
				}
			}
		}
		V = n + m;
		cout << matching() << endl;

		for(int i = 0; i < V; i++) G[i].clear();
	}
	return 0;
}

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

int main() {
    int N;
    cin >> N;
    vector<int> n(N);
    for(int i=0;i<N;i++) cin >> n[i];
    sort(begin(n),end(n));
    int layer = 0;
    int tmp = 0;
    for(int x : n) {
        if(x > tmp) {
            layer++;
            tmp = x;
        }
    }
    cout << layer << endl;
}

Measured memory_bytes: 256
{-# OPTIONS_GHC -O2 #-}
{-# LANGUAGE CPP                   #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE OverloadedStrings     #-}
{-# LANGUAGE RecordWildCards       #-}
{-# LANGUAGE TupleSections         #-}
{-# LANGUAGE TypeFamilies          #-}

import           Control.Applicative
import           Control.Monad
import           Control.Monad.Primitive
import           Control.Monad.ST
import           Control.Monad.State.Strict
import           Data.Bool
import qualified Data.ByteString.Char8       as B
import qualified Data.ByteString.Unsafe      as B
import           Data.Char
import           Data.Function
import qualified Data.IntMap.Strict          as IM
import qualified Data.IntSet                 as IS
import           Data.List
import qualified Data.Map.Strict             as M
import           Data.Monoid
import           Data.Ord
import           Data.Primitive.MutVar
import qualified Data.Set                    as S
import           Data.Tuple
import qualified Data.Vector                 as V
import qualified Data.Vector.Generic         as G
import qualified Data.Vector.Generic.Mutable as GM
import qualified Data.Vector.Unboxed         as U
import qualified Data.Vector.Unboxed.Mutable as UM
import           Debug.Trace
import           Foreign                     hiding (void)
import           Unsafe.Coerce

main :: IO ()
main = do
    cs <- getLine
    k <- readLn :: IO Int
    putStrLn $ solve k cs

solve :: Int -> String -> String
solve k cs = S.toAscList candidates !! (k - 1)
  where
    candidates = S.fromList . concatMap (\t -> filter (not.null) $ map(\i->take i t) [1..5]) $ tails cs

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



Measured memory_bytes: 4348
//Name: IOI Manju
//Level: 2
//Category: 動的計画法,DP
//Note: 

/**
 * 饅頭は高いものから詰めていけばよいことは明らか。
 * したがって詰め方は関係なく、（選んだ箱の総容量分の饅頭の価格）-（選んだ箱のコスト）を最大化する問題になるから、
 * ある容量を実現するためのコストが計算できればよい。
 * これは0-1ナップサック問題であるが、入れる饅頭の個数に対して容量がオーバーしてもよいことから「最低でも容量cを実現するためのコスト」と
 * 読みかえると実装しやすい。
 *
 * オーダーは O(NM)。
 */
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

template <typename T>
struct Maybe {/*{{{*/
    T val;
    bool valid;

    Maybe() : valid(false) {}
    Maybe(T &t) : val(t), valid(true) {}

    T& operator =(const T &rv) {
        val = rv;
        valid = true;
        return val;
    }

    operator T() {
        return valid ? val : T();
    }

    template<typename Cond>
    void update(const T &v, Cond cond) {
        if(!valid || cond(v, val)) {
            val = v;
            valid = true;
        }
    }

    void update(const T &v) {
        update(v, less<T>());
    }
};/*}}}*/

bool solve(bool first) {
    int M, N;
    if(!(cin >> M >> N)) return false;

    vector<long long> ms(M);
    for(int i = 0; i < M; ++i) {
        cin >> ms[i];
    }
    sort(begin(ms), end(ms), greater<long long>());
    for(int i = 1; i < M; ++i) {
        ms[i] += ms[i-1];
    }

    vector<Maybe<long long>> dp(M+1);
    dp[0] = 0;
    for(int _ = 0; _ < N; ++_) {
        int c, e;
        cin >> c >> e;
        for(int i = M; i >= 0; --i) {
            const int prev = max(0, i-c);
            if(dp[prev].valid) dp[i].update(dp[prev] + e);
        }
        for(int i = M-1; i >= 0; --i) {
            if(dp[i+1].valid) dp[i].update(dp[i+1]);
        }
    }
    long long ans = 0;
    for(int i = 0; i <= M; ++i) {
        if(dp[i].valid) {
            ans = max(ans, (i > 0 ? ms[i-1] : 0) - dp[i]);
        }
    }
    cout << ans << endl;
    return true;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout.setf(ios::fixed);
    cout.precision(10);

    bool first = true;
    while(solve(first)) {
        first = false;
    }
    return 0;
}

Measured memory_bytes: 1308
#define _GLIBCXX_DEBUG
#include <iostream>
#include <vector>
#include <stdio.h>
#include <bits/stdc++.h>


using namespace std;
#define ll long long
#define ld long double
#define  P pair<ll,ll>
#define FOR(i,n,m) for(ll i=n; i<(ll)m;i++)
#define FORa(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define FORr(i,m,n) for(ll i=n; i>=(ll)m; i--)
#define FORm(i,m) for(auto i=m.begin();i!=m.end();i++)
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define ALL(c) (c).begin(), (c).end()
#define VEC2(x,a,b) vector<vector<ll>> x = vector<vector<ll>>(a,vector<ll>(b,0))
#define sortAl(v) sort(v.begin(),v.end())
#define sortAlr(v) sort(v.begin(),v.end()); reverse(v.begin(),v.end())
#define cinv(v,n,m) FOR(i,n,m) cin>>v.at(i)
#define coutv(v,n,m) FOR(i,n,m) cout<<v.at(i) <<" "; cout<<endl
#define cout(n) cout<<fixed<<setprecision(n)


//    Edges := 重み付き辺の集合
//    WeightedGraph := 重み付きグラフ
//    UnWeightedGraph := 重み無しグラフ
//    Matrix := 距離行列
template< typename T >
struct edge {
  ll src, to;
  T cost;

  edge(ll to, T cost) : src(-1), to(to), cost(cost) {}

  edge(ll src, ll to, T cost) : src(src), to(to), cost(cost) {}

  edge &operator=(const int &x) {
    to = x;
    return *this;
  }

  operator ll() const { return to; }
};

template< typename T >
using Edges = vector< edge< T > >;
template< typename T >
using WeightedGraph = vector< Edges< T > >;
using UnWeightedGraph = vector< vector< ll > >;
template< typename T >
using Matrix = vector< vector< T > >;


//計算量(VE)
ll INF = numeric_limits< ll >::max();
template< typename T >
vector< T > shortest_path_faster_algorithm(WeightedGraph< T > &g, ll s)
{
  const auto INF = numeric_limits< T >::max();
  vector< T > dist(g.size(), INF);
  vector< ll > pending(g.size(), 0), times(g.size(), 0);
  queue< ll > que;

  que.emplace(s);
  pending[s] = true;
  ++times[s];
  dist[s] = 0;

  while(!que.empty()) {
    ll p = que.front();
    que.pop();
    pending[p] = false;
    for(auto &e : g[p]) {
      T next_cost = dist[p] + e.cost;
      if(next_cost >= dist[e.to]) continue;
      dist[e.to] = next_cost;
      if(!pending[e.to]) {
        if(++times[e.to] >= g.size()) return vector< T >();
        pending[e.to] = true;
        que.emplace(e.to);
      }
    }
  }
  return dist;
}


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll v,e,r;
    cin>>v>>e>>r;
    WeightedGraph<ll> g(v);
    FOR(i,0,e){
      ll in1,in2,c;
      cin>>in1>>in2>>c;
      g[in1].push_back(edge<ll>(in1,in2,c));
    }
    vector<ll> res = shortest_path_faster_algorithm(g,r);
    if(res.size() == 0) cout<<"NEGATIVE CYCLE"<<endl;
    FOR(i,0,res.size()){
      if(INF == res[i]) cout<<"INF"<<endl;
      else cout<<res[i]<<endl;
    }
}



Measured memory_bytes: 3324
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC154
{
    class Program
    {
        static void Main(string[] args)
        {
            a();
        }

        public static void a()
        {
            string[] st = Console.ReadLine().Split(' ');
            int[] ab = Console.ReadLine().Split(' ').Select(t => int.Parse(t)).ToArray();
            string u = Console.ReadLine();
            if(st[0] == u)
            { ab[0]--; }
            else
            { ab[1]--; }
            Console.WriteLine("{0} {1}", ab[0], ab[1]);
        }
    }
}


Measured memory_bytes: 13396
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

int main() {
   int N;
   string A, B, C;
   cin >> N;
   cin >> A >> B >> C;
   int ans = 0;
   for (int i = 0; i < N; i++) {
      if (A[i] == B[i] && B[i] == C[i]);
      else if (A[i] == B[i] || B[i] == C[i] || C[i] == A[i]) ans++;
      else ans += 2;
   }
   cout << ans << endl;
   return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <vector>
#include <iomanip>
using namespace std;

int main(int argc, char *argv[]) {
	int N;
	cin >> N;
	vector<int> x(N), y(N);
	for(int i=0;i<N;++i) {
		cin >> x[i] >> y[i];
	}
	double ans = 0;
	for(int i=0;i<N;++i) {
		for(int j=0;j<i;++j) {
			double dx = x[i] - x[j], dy = y[i] - y[j];
			double d = sqrt(dx*dx+dy*dy);
			ans += d * (1. / N) * 2;
		}
	}
	cout << setprecision(10) << ans << endl;
	return 0;
}


Measured memory_bytes: 256