akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
 
#define f first
#define s second
#define pb push_back
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
 
const int N = (int)1e5 + 123, inf = 1e9, mod = 1e9 + 7;
const ll INF = 1e18;
           
int kol;
          
int n;

int ans;

int a[N];             

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


Measured memory_bytes: 640
import java.util.Scanner;
import java.lang.Math;

class Main{
	public static void main(String[] args){

	Scanner sc = new Scanner(System.in);
	
	double r = sc.nextDouble();
	
	System.out.printf("%.5f %.5f",r*r*Math.PI, r*2*Math.PI);
	
	sc.close();
	}
}


Measured memory_bytes: 28228
#define D(x) cout << #x " = " << x << endl
#define DD(x, y) cout << "(" #x ", " #y ") = (" << x << ", " << y << ")" << endl
#define DDD(x, y, z) cout << "(" #x ", " #y ", " #z ") = (" << x << ", " << y << ", " << z << ")" << endl
#define DV(v) for (auto __macro_vi : v){ cout << __macro_vi << " ";} cout << endl;
#define DA(a, n) for (int __macro_i = 0; __macro_i < n; ++__macro_i) { cout << a[__macro_i] << " "; } cout << endl;
#define REP(i, n) for (int i = 0; i < n; ++i)
#define ALL(v) (v).begin(), (v).end()
#include<iostream>
#include<vector>
#include<cassert>
#include<cmath>

using namespace std;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a, b;
    cin >> a >> b;
    cout << (a + b == 15 ? '+' : a * b == 15 ? '*' : 'x') << endl;
}


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

ll solve(const int n, const int m, ll x, vector<ll> c, vector<vector<ll>> a) {
  const int bit = 1 << n;
  ll res = -1;
  for(int i=0; i< bit; i++) {
    ll cost = 0;
    vector<ll> temp(m, 0);
    for(int j=0;j<n;j++) {
      if(i & (1 << j)) {
	cost += c[j];
	for(int k=0;k<m;k++) {
	  temp[k] += a[j][k];
	}
      }
    }
    for(int j=0;j<m;j++) {
      if(temp[j] < x) {
	break;
      }
      if(j==m-1) {
	res = res == -1 ? cost : min(cost, res);
      }
    }
  }
  return res;
}

int main() {
  int n, m;
  cin >> n >> m;
  ll x;
  cin >> x;
  vector<ll> c(n);
  vector<vector<ll>> a(n, vector<ll>(m));
  for(int i=0;i<n;i++) {
    cin >> c[i];
    for(int j=0;j<m;j++) {
      cin >> a[i][j];
    }
  }
  cout << solve(n, m, x, c, a);
}

Measured memory_bytes: 3628
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <queue>

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define mod (ll)(1e9+7)
#define FIX(a) ((a)%mod+mod)%mod
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define fi first
#define se second
#define pb push_back
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m;
    cin >> n >> m;
    if(n==m){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;

    }

    return 0;
}

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

int main(){
	int a;string y;
	cin>>y>>a;
	int cnt=0;
	for(int i=0;i<a;i++){
		string b,c="";
		cin>>b;
		c.clear();
		b+=b;
		for(int j=0;j<14;j++){
			for(int k=j;k<y.size()+j;k++){
				c+=b[k];
			}
			if(y==c){
			cnt++;break;
			}
			c="";
		}
	}
	cout<<cnt<<endl;
	return 0;
}

Measured memory_bytes: 1220
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = s; i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << endl;
#define CFYN(n) cout << ( (n) ? "YES":"NO") << endl;
#define OUT(n) cout << (n) << endl;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;


int main(void)
{
    IOS
    int n; cin >> n;
    vector<int> v(n+2); // 0 v[1] v[2] ... v[n] 0
    vector<int> d(n+1); // v[i] - v[i-1]
    int dsum = 0;
    REP(i,n) {
        cin >> v[i+1];
        d[i] += abs(v[i+1] - v[i]); 
        dsum += d[i];
    }
    d[n] = abs(v[n+1] - v[n]);
    dsum += d[n];

    REP(i,n) {
        cout << dsum - (d[i] + d[i+1]) + abs(v[i+2] - v[i]) << endl;
    }
    
    return 0;
}

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

using ll = long long;

int main() {
    int N;
    string S, T;
    cin >> N >> S >> T;
    rep(i, N) cout << S[i] << T[i];
    cout << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <stack>
#include <istream>
#include <map>
#include <set>
#include <queue>
#define rep0(i,n) for (int i = 0; i <= (n); ++i)
#define rep1(i,n) for (int i = 1; i <= (n); ++i)
#define REP(a,b) for (int i = a; i <= (b); ++i) 
#define mREP(a,b) for (int i = a; i == (b); --i) 
typedef long long ll;
using namespace std;
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
/*
	　　　  　 ,ﾍ／L──- 、
	　　　   　Lﾆ)r_」=＝= ｲ
	　　 　,ﾍ、i ﾉノλﾉﾊﾉﾍ
	　　   ,'　｀(ﾊﾘ ﾟ ヮﾟﾉi)　',
	　　 .i　　 >〈(つ,i!と)　　i
	　　  vﾍγk´_/___i,ゝﾍノ
	　　　　　 ｀ﾞr_,ｨ_ｧﾞ´
*/
string s;
cin >> s;
int s_size = s.length();
int ans  = 1e7;
int temp = 0;
rep0(i, s_size - 3) {
	temp = ((s[i] - '0') * 100) + ((s[i + 1] - '0') * 10) + (s[i + 2] - '0');
	int a = abs(temp - 753);
	ans = min(a, ans);
}
cout << ans << endl;
return 0;
}


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

int main(){
    int N; cin>>N;
    vector<ll> bl(N+1,0),A(N+1,0);
    
    rep(i,N){
        int x; cin>>x;
        bl[x]++;
        A[i+1]=x;
    }
    
    //ボールを除く前
    ll sum=0;
    for(int i=1; i<=N; i++){
        if(bl[i]>=2){
            sum += (bl[i]*(bl[i]-1))/2;
        }
    }
    
    //ｋ番目のボールを除いたとき
    for(int k=1; k<=N; k++){
        ll ans=sum;
        if(bl[A[k]]>=2){
            ans -= (bl[A[k]]-1);
        }
        cout << ans << endl;
    }
}


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

bool isPal(string s) {
  string t = s;
  reverse(t.begin(), t.end());
  return s == t;
}

int main() {
  string S;
  bool ans = true;

  cin >> S;
  int N = S.length();
  string leftSub = S.substr(0, (N-1)/2);

  if (isPal(S) && isPal(leftSub)) {
    cout << "Yes" << endl;
    return 0;
  }

  cout << "No" << endl;
}


Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;

int n,m,ans,t,w;
int b[4010],c[4010],q[4010],f[4010];
char a[4010][4010];

int main()
{int i,j,flag;
 
 scanf("%d%d",&n,&m);
 for(i=1;i<=n;i++)
 	scanf("%s",a[i]+1);
 for(i=1;i<=n;i++) b[i]=1;
 ans=max(n,m);
 for(j=m;j>=1;j--)
 {	for(i=2;i<=n;i++)
 	{	flag=(a[i][j]==a[i-1][j]);
 		if(flag==b[i])
			c[i]++;
		else
		{	c[i]=1;
			b[i]=flag;
		}
	}
	
	//for(i=1;i<=n;i++)
	//	cout<<c[i]<<" ";
	//cout<<endl;
	
	memset(f,0,sizeof(f));
	t=1;
	w=1;
	q[t]=1;
	for(i=2;i<=n;i++)
	{	while(t<=w && c[q[w]]>=c[i]) w--;
		f[i]=-q[w];
		q[++w]=i;
	}
	t=1;
	w=1;
	q[t]=n+1;
	for(i=n;i>=1;i--)
	{	while(t<=w && c[q[w]]>=c[i]) w--;
		f[i]+=q[w];
		q[++w]=i;
	}
	for(i=1;i<=n;i++)
		ans=max(ans,f[i]*c[i]);
		
	//cout<<ans<<endl;	
 }
 printf("%d\n",ans);
 return 0;
}

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

using namespace std;
using ll = long long;

bool is_prime(ll v)
{
        for (ll i = 2; i * i <= v; ++i) {
                if (v % i == 0)
                        return false;
        }
        return true;
}

int main() {
        ll x;
        cin >> x;
        while(true) {
                if (is_prime(x))
                        break;
                ++x;
        }
        cout << x << endl;
        return 0;
}


Measured memory_bytes: 256
s = list(input())
'''
for i in range(len(s)-1):
	if s[i] == "?":
		if s[i+1] == "D":
			s[i] = "P"
		elif s[i+1] == "?":
			s[i] = "P"
			s[i+1] = "D"
			i+=1
		else:
			s[i] = "D"
if s[-1] == "?":
	s[-1] = "D"
	'''
for i in range(len(s)):
	if s[i] == "?":
		s[i] = "D"
print("".join(s))


Measured memory_bytes: 10820
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

typedef long long ll;
typedef uint64_t ull;
typedef pair<int, int> P;
typedef pair<int, double> Pid;
typedef pair<double, int> Pdi;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
typedef pair<int, pair<int, int>> PP;
typedef pair<P, int> PPi;
constexpr double PI = 3.1415926535897932;   // acos(-1)
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define chadd(x, y) x = (x + y) % mod

struct UnionFind{
    int sz;     // vertex number
    vector<int> par;
    vector<int> rank;

    UnionFind(int n) : sz(n) {
        par.resize(sz);
        rank.assign(sz, 0);
        for(int i = 0; i < sz; ++i){
            par[i] = i;
        }
    }

    int find(int x){
        if(par[x] == x) return x;
        else    return par[x] = find(par[x]);
    }

    bool same(int x, int y){
        return find(x) == find(y);
    }

    void unite(int x, int y){
        x = find(x), y = find(y);
        if(x == y)  return;
        if(rank[x] < rank[y])   par[x] = y;
        else{
            par[y] = x;
            if(rank[x] == rank[y])  ++rank[x];
        }
    }
};

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

    int n, m;
    cin >> n >> m;
    vector<int> p(n);
    for(int i = 0; i < n; ++i)  cin >> p[i], --p[i];
    UnionFind uf(n);
    for(int i = 0; i < m; ++i){
        int x, y;
        cin >> x >> y;
        --x, --y;
        uf.unite(x, y);
    }
    int ans = 0;
    for(int i = 0; i < n; ++i)  if(uf.same(p[i], i))    ++ans;
    cout << ans << endl;
}

Measured memory_bytes: 1408
#include <iostream>
#include <vector>
#include <string>
#include <sstream>


void getInput(std::vector<int> *v);
void dispV(std::vector<int> v);
void S(int n, int *s);

int main(void)
{
	//std::vector<std::string> v;
	std::vector<int> v;
	int num, s;

	// get array length
	getInput(&v);
	num = v[0];
	S(num, &s);

	if(num % s == 0) std::cout << "Yes" << std::endl;
	else std::cout << "No" << std::endl;

	/*
	while(v[0][i] != '\0') {
		//std::cout << v[0][i] << std::endl;
		if(v[0][i] == '+') num++;
		if(v[0][i] == '-') num--;
		i++;
	}

	std::cout << num << std::endl;
	*/



}

void getInput(std::vector<int> *v)
{
	std::string s, buf;
	std::getline(std::cin, s);
	std::stringstream ss(s);
	
	while(std::getline(ss, buf, ' ')) {
		(*v).push_back(std::stoi(buf));
	}
}

void dispV(std::vector<int> v)
{
	std::cout << "[";
	for(int i = 0; i < v.size(); i++) {
		//std::cout << i << ":" << v[i] << std::endl;
		std::cout << v[i] << ",";
	}
	std::cout << "]" << std::endl;
}

void S(int n, int *s) {
	while(n != 0.0) {
		(*s) += n % 10;
		n /= 10;
	}
}













Measured memory_bytes: 256
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <array>
#include <bitset> 
#include <unordered_map>
#include <random>

using namespace std;
typedef long long LL;
typedef pair<int,int> P;

const int L=301;
const LL M=1e9+7;
LL dp[L][L][L];
vector<P> ps[L];
int main() {
	dp[0][0][0]=1;
	int N,K;
	scanf("%d%d",&N,&K);
	for(int i=0;i<K;i++){
		int l,r,x;
		scanf("%d%d%d",&l,&r,&x);
		ps[r].push_back(P(l,x));
	}
	LL ret=0;
	for(int i=0;i<=N;i++){
		for(int j=i;j<=N;j++){
			for(int k=j+1;k<=N;k++){
				bool ok=true;
				for(auto p:ps[k]){
					switch(p.second){
						case 1:
							if(p.first<=j){
								ok=false;
							}
							break;
						case 2:
							if(p.first<=i||
								j<p.first){
								ok=false;
							}
							break;
						case 3:
							if(i<p.first){
								ok=false;
							}
							break;
					}
				}
				if(!ok)continue;
				if(j==k-1){
					for(int l=0;l<=i;l++){
						dp[i][j][k]+=dp[l][i][j];
						dp[i][j][k]%=M;
					}
					for(int l=i+1;l<j;l++){
						dp[i][j][k]+=dp[i][l][j];
						dp[i][j][k]%=M;
					}
				}
				else{
					dp[i][j][k]=dp[i][j][k-1];
				}
				if(k==N){
					if(j>0){
						ret+=6*dp[i][j][k]%M;
						ret%=M;
					}
					else{
						ret+=3*dp[i][j][k]%M;
						ret%=M;
					}
				}
				//cerr << i << ", " << j << ", " << k << ": " << dp[i][j][k] << endl;
			}
		}
	}
	printf("%lld\n",ret);

	return 0;
}



Measured memory_bytes: 213248
#include<bits/stdc++.h>
#define REP(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
const ll MOD = 1000000007;

int main() {
  int n, m, c, s = 0, cnt = 0;
  cin >> n >> m >> c;
  int a, b[m];
  REP(i, m) cin >> b[i];
  REP(i, n) {
    s = 0;
    REP(i, m) {
      cin >> a;
      s += a * b[i];
    }
    if (s + c > 0) ++cnt;
  }

  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 256
import Control.Applicative

import Data.Char
    (digitToInt)

type Problem = [String]

type Result = [Int]

solve :: Problem -> Result

solve xs
    = map (\x -> sum $ map digitToInt x) xs

output :: [Int] -> String

output xs
    = init.concat $ map (\x -> show x ++ "\n") xs

input :: IO [String]

input
    = inputData []

inputData :: [String] -> IO [String]

inputData xs
    = do
        text <- getLine
        if text == "0"
            then return xs
            else inputData $ xs ++ [text]

main :: IO ()

main
    = putStrLn.output =<< solve <$> input

Measured memory_bytes: 4064
{-# OPTIONS_GHC -O2 -funbox-strict-fields #-}
import           Control.Monad (replicateM)
import           Data.Monoid   ((<>))

main :: IO ()
main = do
  [n, a, b, c] <- map read . words <$> getLine
  ls <- replicateM n readLn
  print $ solve n a b c ls

solve :: Int -> Int -> Int -> Int -> [Int] -> Int
solve _ a b c = minimum . dfs 0 0 0
  where
    dfs x y z []
      | x == 0 || y == 0 || z == 0 = []
      | otherwise = [abs (x - a) + abs (y - b) + abs (z - c) - 30]
    dfs x y z (l:ls) = d1 <> d2 <> d3 <> d4
      where
        d1 = dfs x y z ls
        d2 = map (+ 10) $ dfs (x + l) y z ls
        d3 = map (+ 10) $ dfs x (y + l) z ls
        d4 = map (+ 10) $ dfs x y (z + l) ls


Measured memory_bytes: 2300
#include <iostream>
#include <string>
#include <cmath>
#include <iomanip>

using namespace std;

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

    double score = 0.0;

    for (int i = 1; i <= n; i++) {
        if (i >= k) {
            score += 1;
        }
        else {
            int r = ceil(log2(1.0 * k / i));
            score += pow(0.5, r);
        }
    }
    score /= n;

    cout << std::setprecision(12) << score << endl;
    

    return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define all(v) v.begin(), v.end()
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vec;
typedef vector<vec> mat;
template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr int getmod() { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};
const int MOD = 1000000007;
using mint = Fp<MOD>;
mint dp[200001][2][100];
int main(){
    string s;
    ll d,x;
    cin>>s>>d;
    dp[0][1][0]=1;
    rep(i,s.size())rep(j,2)rep(k,d){
        if(j==0) x=9;
        else x=s[i]-'0';
        rep(l,x+1) dp[i+1][j&&l==x][(k+l)%d]+=dp[i][j][k];
    }
    cout<<dp[s.size()][0][0]+dp[s.size()][1][0]-1<<"\n";
}

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

int main() {
  string s;
  cin >> s;
  string t;
  t = s;

  sort(t.begin(), t.end());
  t.erase(unique(t.begin(), t.end()), t.end());
  //cout << t.size() << endl;
  int a=0, b=0;
  for(int i = 0; i < 2; i++) {
      for(int j = 0; j < s.size(); j++) {
          if(t[i] == s[j]){
              a++;
          }
      }
      if(a != 2) {
          cout << "No" << endl;
          return 0;
      }
      a = 0;
  }
  cout << "Yes" << endl;

  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include <algorithm>
const int MAX = 1299709;
using namespace std;

bool isPrime[MAX+5];
int seqPrime[MAX+5];
int ITR = 0;

void  eratos() {
	// 初期化
	for(int i=0;i<=MAX;i++) {
		isPrime[i] = true;
	}
	for(int i=2;i<=MAX;i++) {
		if(isPrime[i]) {
			seqPrime[ITR++] = i;
			for(int j=2*i;j<=MAX;j+=i) {
				isPrime[j] = false;
			}
		}
	}
}

int main()
{
	eratos();
	int k;
	while(1) {
		cin >> k;
		if(k==0) break;
		auto now = upper_bound(seqPrime, seqPrime+ITR, k);
		auto before = now-1;
		if(*before == k) cout << 0 << endl;
		else cout << (*now-*before) << endl;
	}
}


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

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

    vector<int> p(N);
    rep(i, N) cin >> p[i];

    for (int i=0; i<N; ++i) {
        for (int j=0; j<N; ++j) {
            swap(p[i], p[j]);

            bool ok = true;
            rep(i, N-1) {
                if (p[i] > p[i+1]) ok = false;
            }

            if (ok) {
                cout << "YES" << endl;
                return 0;
            }

            swap(p[i], p[j]);
        }
    }

    cout << "NO" << endl;

}


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

using namespace std;

using i64 = int64_t;
using P = pair<i64, i64>;

struct edge {
    i64 from, to, cost;
    edge(i64 from, i64 to) : from(from), to(to), cost(1) {}
    edge(i64 from, i64 to, i64 cost) : from(from), to(to), cost(cost) {}
};
using Graph = vector<vector<edge>>;

constexpr i64 INF = std::numeric_limits<i64>::max();
constexpr i64 SINF = std::numeric_limits<i64>::max() / 10;
const i64 dx[4] = { 0,1,0,-1 }, dy[4] = { -1,0,1,0 };
//const i64 dx[5] = {-1,0,0,0,1}, dy[5] = {0,-1,0,1,0};
//const i64 dx[8] = {-1,0,1,1,1,0,-1,-1}, dy[8] = {1,1,1,0,-1,-1,-1,0};
//const i64 dx[9] = {-1,0,1,1,1,0,-1,-1,0}, dy[9] = {1,1,1,0,-1,-1,-1,0,0};

#define rep(i, n) for(i64 i = 0; i < n; ++i)

// http://beet-aizu.hatenablog.com/entry/2018/04/08/145516
template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }

template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
    for (auto& e : t) fill_v(e, v);
}

struct IoSetup {
    IoSetup() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
        cerr << fixed << setprecision(10);
    }
} iosetup;

void solve(i64 n, vector<i64> k){
    i64 ans = 1;
    bool flag = false;
    rep(i, n){
        if(k[i] != 0) ++ans;
        if(k[i] >= 2) flag = true;
    }
    if(flag) cout << ans << endl;
    else cout << "NA" << endl;
}

int main(){
    while(true){
        i64 n;
        cin >> n;
        if(n == 0) break;
        vector<i64> k(n);
        rep(i, n) cin >> k[i];
        solve(n, k);
    }
}


Measured memory_bytes: 3336
#include <stdio.h>

int main(void)
{
    int i, j, a[8][8];

    for (;;) {
        for (i = 0; i < 8; i++)
            for (j = 0; j < 8; j++)
                if (scanf("%1d", &a[i][j]) == EOF)
                    return 0;

        for (i = 0; i < 8; i++)
            for (j = 0; j < 8; j++)
                if (a[i][j] == 1)
                    goto loop_done;

loop_done:
        if (i <= 6 && j <= 6 && a[i][j+1] && a[i+1][j] && a[i+1][j+1])
            printf("A\n");
        else if (i <= 4 && a[i+1][j] && a[i+2][j] && a[i+3][j])
            printf("B\n");
        else if (j <= 4 && a[i][j+1] && a[i][j+2] && a[i][j+3])
            printf("C\n");
        else if (i <= 5 && j >= 1 && a[i+1][j-1] && a[i+1][j] && a[i+2][j-1])
            printf("D\n");
        else if (i <= 6 && j <= 5 && a[i][j+1] && a[i+1][j+1] && a[i+1][j+2])
            printf("E\n");
        else if (i <= 5 && j <= 6 && a[i+1][j] && a[i+1][j+1] && a[i+2][j+1])
            printf("F\n");
        else
            printf("G\n");
    }
}

Measured memory_bytes: 576
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
    ll n,i,j,mx,a;
    string s;
    while(cin>>n)
    {
        a=0;
        mx=0;
        cin>>s;
        for(i=0;i<s.length();i++)
        {
            if(s[i]=='I')a++;
            else a--;
            mx=max(a,mx);
        }
        cout<<mx<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
/*
    Author: Alam Khan
    AUST CSE 40th Batch

*/

#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef deque<ll> dl;
typedef stack<ll> stl;
typedef set<ll> sl;
typedef map<string, ll> msl;
typedef map<ll,ll> mll;
typedef tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
#define sf(n)     scanf("%lld",&n)
#define sff(n,m)     scanf("%lld %lld",&n,&m)
#define sfff(n,m,r)     scanf("%lld %lld %lld",&n,&m,&r)
#define sfs(n)     scanf("%s",n)
#define pf(n)     printf("%lld\n",n)
#define pff(n,m)     printf("%lld %lld\n",n,m)
#define pfff(n,m,r)     printf("%lld %lld %lld\n",n,m,r)
#define pfs(n)     printf("%s\n",n)
#define pfcs(i,n)     printf("Case %lld: %lld\n",i,n)
#define pb     push_back
#define prf     printf
#define inf     2e18
#define low     -1000000000000
#define PI        acos(-1.0)
#define rep1(i,n) for(i=1;i<n;i++)
#define rep0(i,n) for(i=0;i<n;i++)
#define rep(i,a,n) for(i=a;i<n;i++)
#define repe1(i,n) for(i=1;i<=n;i++)
#define repe0(i,n) for(i=0;i<=n;i++)
#define repe(i,a,n) for(i=a;i<=n;i++)
#define endl  "\n"
#define FAST  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define fr freopen("input.txt","r",stdin)
#define fw freopen("output.txt","w",stdout)
#define all(v) v.begin(), v.end()
ll a[200009],diff[200009];
vector<ll> v[800009];
void build(ll att,ll L,ll R)
{
    if(L==R)
    {
        v[att].pb(diff[L]);
        return;
    }

    ll mid = (L+R)/2;
    build(att*2,L,mid);
    build(att*2+1,mid+1,R);
    merge(all(v[att*2]), all(v[att*2+1]), back_inserter(v[att]));
}
ll query(ll att,ll L,ll R,ll l,ll r,ll p)
{
    if(l>R || r<L)
        return 0;
    if(l<=L && r>=R)
    {
       // for(ll i=0;i<v[att].size();i++)
         //   cout<<v[att][i]<<" ";
        //cout<<endl;
        ll x = lower_bound(v[att].begin(),v[att].end(),p) - v[att].begin();
        ll y = upper_bound(v[att].begin(),v[att].end(),p) - v[att].begin();
        return y-x;
    }
    ll mid = (L+R)/2;
    ll x = query(att*2,L,mid,l,r,p);
    ll y = query(att*2+1,mid+1,R,l,r,p);

    return x+y;
}
int main()
{
    ll i,n,t,k,j,x=0,y=0,m;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(i=1;i<=n;i++)
    {
        diff[i] = i-a[i];
    }
    build(1,1,n);
    ll ans = 0;
    for(i=1;i<=n;i++)
    {
        x = i+a[i];
        if(x<=n)
            ans+= query(1,1,n,x,n,x);
    }
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 69028
#include<bits/stdc++.h>
using namespace std;
int main(){
	int N,M;cin>>N>>M;
	int l=0,r=N+1;int a,b;
	for(int i=0;i<M;i++){
		cin>>a>>b;
		l=max(l,a);
		r=min(r,b);
	}if(l<=r){
		cout<<r-l+1<<endl;
	}else{
		cout<<0<<endl;
	}
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<string>
#include<algorithm>
#include<functional>
#include<math.h>
#include<unordered_set>
using namespace std;
const int MAX = 100001;

int main() {
	int N;
	vector<int> parts[3];
	int table1[MAX] = { 0 };
	int table2[MAX] = { 0 };

	cin >> N;
	for (int i = 0; i < 3;i++){
		for (int j = 0; j < N; j++) {
			int n;
			cin >> n;
			parts[i].push_back(n);
		}
	}
	

	for (int i = 0; i < 3; i++) {
		sort(parts[i].begin(),parts[i].end());
	}

	for (int i = 0; i < N; i++) {
		vector<int>::iterator it = lower_bound(parts[0].begin(), parts[0].end(), parts[1][i]);
		table1[i] = distance(parts[0].begin(), it);
	}

	for (int i = 0; i < N; i++) {
		vector<int>::iterator it = upper_bound(parts[2].begin(), parts[2].end(), parts[1][i]);
		table2[i] = N - distance(parts[2].begin(), it);
	}

	long long ans = 0;
	for (int i = 0; i < N; i++) {
		ans += (long long)table1[i] * table2[i];
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 2552
#include<bits/stdc++.h>
using namespace std;
int n,m,w[105],v[105],f[100005];
int main() {
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>w[i]>>v[i];
	memset(f,0x3f,sizeof(f)),f[0]=0;
	for(int i=1;i<=n;i++){
		for(int j=100000;j>=v[i];j--)f[j]=min(f[j],f[j-v[i]]+w[i]);
	}
	int ans=0;
	for(int i=1;i<=100000;i++)if(f[i]<=m)ans=i;
	cout<<ans;
}

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

using namespace std;
using llong = long long;
using ldbl = long double;
using lpair = pair<llong, llong>;

#define ALL(x) x.begin(), x.end()

const llong inf = 1'000'000'000'000'007ll;
const llong mod = 1e9+7;

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

	cout << N*N*N << endl;

	return 0;
}

Measured memory_bytes: 256
S = input()
S = "".join(list(S.replace("A","*").replace("C","*").replace("T","*").replace("G","*")))
count = 0
if S.count("*"*10) == 1:
  count = 10
elif S.count("*"*9) == 1:
  count = 9
elif S.count("*"*8) == 1:
  count = 8
elif S.count("*"*7) == 1:
  count = 7
elif S.count("*"*6) == 1:
  count = 6
elif S.count("*"*5) == 1:
  count = 5
elif S.count("*"*4) >= 1:
  count = 4
elif S.count("*"*3) >= 1:
  count = 3
elif S.count("*"*2) >= 1:
  count = 2
elif S.count("*"*1) >= 1:
  count = 1
else:
  count = 0
print(count)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#include<string.h>
 
typedef long long int ll;
#define all(x) (x).begin(), (x).end()
 
using namespace std;

int nxt() {
    int x;
    cin >> x;
    return x;
}

ll nxtl(){
    ll x;
    cin>>x;
    return x;
}
 
void SieveOfEratosthenes(int n,vector <int> &primes) 
{ 
    // Create a boolean array "prime[0..n]" and initialize 
    // all entries it as true. A value in prime[i] will 
    // finally be false if i is Not a prime, else true. 
    bool prime[n+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=n; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) 
        { 
            // Update all multiples of p greater than or  
            // equal to the square of it 
            // numbers which are multiple of p and are 
            // less than p^2 are already been marked.  
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
  
    // Print all prime numbers 
    for (int p=2; p<=n; p++) 
       if (prime[p]) 
          primes.push_back(p);
} 
 
ll max(ll a,ll b)
{
    if(a>b)
        return a;
    return b;
}
 
ll power(ll x, ll y,ll mod) 
{ 
    ll temp; 
    if( y == 0) 
        return 1; 
    temp = power(x, y/2,mod); 
    if (y%2 == 0) 
        return (temp*temp)%mod; 
    else
        return (((x*temp)%mod)*temp)%mod; 
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n=nxt(),t=nxt();
    vector <int> v(n);
    generate(all(v),nxt);
    map <int,int> m1;
    map <int,int,greater<int> > m2;
    m2[v[n-1]]=1;
    int d=INT_MIN;
    for(int i=0;i<n-1;i++)
        m1[v[i]]+=1;
    for(int i=n-2;i>=0;i--)
    {
        d=max(d,m2.begin()->first-m1.begin()->first);
        m1[v[i]]-=1;
        m2[v[i]]+=1;
        if(m1[v[i]]==0)
            m1.erase(v[i]);
    }

    int test=0;
    m1.clear();m2.clear();

    m2[v[n-1]]=1;
    for(int i=0;i<n-1;i++)
        m1[v[i]]+=1;
    map <int,int> change;
    //cout<<d<<endl;
    for(int i=n-2;i>=0;i--)
    {
        int temp=m2.begin()->first-m1.begin()->first;
        if(temp==d)
        {
            if(m1.begin()->second>m2.begin()->second)
            {
                int val=m1.begin()->first;
                int count=m1.begin()->second;
                m1.erase(val);
                m1[val+1]+=count;
                change[val]=val+1;
                test+=count;
            }
            else
            {
                int val=m2.begin()->first;
                int count=m2.begin()->second;
                m2.erase(val);
                m2[val-1]+=count;
                test+=count;
            }
        }
        int val=v[i];
        if(change.find(val)!=change.end())
            val=change[val];
        m1[val]-=1;
        m2[val]+=1;
        if(m1[val]==0)
            m1.erase(val);
        //cout<<i<< " "<<test<<endl;

    }
    cout<<test<<endl;


    
    return 0;   
}




 
 


Measured memory_bytes: 5376
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

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

int main(){
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);
  double a;
  cin>>a;
  cout<<2*3.1415926*a;

}


Measured memory_bytes: 3800
#include<iostream>
#include<queue>
using namespace std;
priority_queue<int>q; //优先队列默认从大到小 
int main()
{
	int n,m,a,t;
	long long ans = 0;
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		cin>>a;
		q.push(a);
	}
	for(int i=0;i<m;i++)
	{
		t = q.top()/2;
		q.pop();
		q.push(t);
	}
	while(q.empty()==0)
	{
		ans+=q.top();
		q.pop();
	}
	cout<<ans;
	return 0;
 } 

Measured memory_bytes: 892
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 50;
const int mod = 1e9;
int main()
{
    std::ios::sync_with_stdio(false);
    int n, k, s;
    cin >> n >> k >> s;
    for(int i = 0;i < k;i++) cout << s << " ";
    for(int i = k;i < n;i++) cout << (2 * s % mod) + 1 << " ";
    return 0;
}


Measured memory_bytes: 1280
import math,string,itertools,fractions,heapq,collections,re,array,bisect,random
def Main(n):
  A, B = [], []
  for _ in range(n):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

  cnt = 0
  for i in reversed (range(n)):
    A[i] += cnt
    if A[i] % B[i] != 0:
      cnt += B[i] - (A[i] % B[i])

  print(cnt)

if __name__ == '__main__':
  T = int(input())
  Main(T)

Measured memory_bytes: 19116
import java.util.Scanner;

public class Main {
	void run() {
		Scanner scan = new Scanner(System.in);
		int x = scan.nextInt();
		int y = scan.nextInt();
		if (y > x) {
			int swap = x;
			x = y;
			y = swap;
		}
		while (x > y) {
			int n = x % y;
			if (n == 0) break;
			x = y;
			y = n;
		}
		System.out.println(y);
	}
	public static void main(String[] args) {
		new Main().run();
	}
}



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

l = [[0, 0, 0] for _ in range(n-1)]

for i in range(n-1):
  c, s, f = map(int, input().split())
  l[i][0] = c
  l[i][1] = s
  l[i][2] = f

for i in range(n-1):
  t = l[i][1] + l[i][0]
  for j in range(i+1, n-1):
    if t%l[j][2] == 0 and t >= l[j][1]:
      pass
    elif t%l[j][2] != 0 and t >= l[j][1]:
      t = (t//l[j][2]+1)*l[j][2]
    else:
      t = l[j][1]
    t += l[j][0]
  print(t)
else:
  print(0)

Measured memory_bytes: 41964
#include <iostream>
using namespace std;
int main() {
    int r,D,x2000;
    cin >> r >> D >> x2000;
    
    int xtmp=x2000;
    
    for(int i=0;i<10;i++)
        cout << ((xtmp*=r)-=D) << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
int main(void){
    int a[6];
    char ope[100];
    int i,oplen,tmp;
    for(i = 0;i<6;i++){
        scanf("%d",&a[i]);
    }
    scanf("%s",ope);
    oplen = strlen(ope);
    for(i=0;i<oplen;i++){
        switch(ope[i]){
        case 'E' : tmp = a[0];
                    a[0] = a[3];
                    a[3] = a[5];
                    a[5] = a[2];
                    a[2] = tmp;
                    break;
        case 'W' : tmp = a[0];
                    a[0] = a[2];
                    a[2] = a[5];
                    a[5] = a[3];
                    a[3] = tmp;
                    break;
        case 'N' : tmp = a[0];
                    a[0] = a[1];
                    a[1] = a[5];
                    a[5] = a[4];
                    a[4] = tmp;
                    break;
        case 'S' : tmp = a[0];
                    a[0] = a[4];
                    a[4] = a[5];
                    a[5] = a[1];
                    a[1] = tmp;
                    break;
        }
    }
    printf("%d\n",a[0]);
    return 0;
}

Measured memory_bytes: 596
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector> 
#include<limits>
#include<numeric>
#include<type_traits>
#include<math.h>
#include<fstream>
#include<set>
#include<queue>
using namespace std;
typedef long long ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define out(str) cout << str << endl
#define ALL(a) (a).begin(),(a).end()
#define INF (1<<29)

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; }

int gcd(int a, int b) {
  return b != 0 ? gcd(b, a % b) : a;
}

int now=0,N,A;

int main(){
    cin>>N;
    rep(i,N){
        cin>>A;
        now = gcd(A,now);
    }
    out(now);
    

}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<vector>
#include<math.h>
#include<map>
#include<queue> 
#include<algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;
typedef pair<int,int> pii;
typedef long long ll;
const int mod=1000000007;

int n;
char mp[5][60];

int main ()
{
	while (scanf ("%d",&n)!=EOF){
		for (int i=1;i<=2;i++){
			scanf ("%s",mp[i]+1);
		}
		int first;
		ll ans;
		if (mp[1][1]==mp[2][1]){
			ans=3;
			first=2;
		}else {
			ans=6;
			first=3;
		}
		for (int i=first;i<=n;){
			if (mp[1][i-1]==mp[2][i-1]){
				if (mp[1][i]==mp[2][i]){
					ans=ans*2%mod;
					i++;
				}else {
					ans=ans*2%mod;
					i+=2;
				}
			}else {
				if (mp[1][i]==mp[2][i]){
					i++;
				}else{
					ans=ans*3%mod;
					i+=2;
				}
			}
		}
		printf ("%lld\n",ans);
	}
	
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#define mk make_pair
#define pb push_back
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<ll, ll> pos;
const ll N = 200010, MOD = 1000000007;

ll n, m, dp[1 << 12];
pos key[1001];

ll mn(ll v1, ll v2) {
	if (v1 == -1)return v2;
	if (v2 == -1)return v1;
	return min(v1, v2);
}

int main() {
	memset(dp, -1, sizeof(dp));
	dp[0] = 0;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		ll v,v2=0;
		cin >> key[i].first >> v;
		for (; v > 0; v--) {
			ll v1; cin >> v1;
			v2 |= ((ll)1 << (v1 - 1));
		}
		key[i].second = v2;
	}
	for (int s = 0; s < (1 << n); s++) {
		if (dp[s] == -1)continue;
		for (int i = 0; i < m; i++) {
			dp[s | key[i].second] = mn(dp[s | key[i].second], dp[s] + key[i].first);
		}
	}
	cout << dp[(1 << n) - 1] << endl;
	return 0;
}



Measured memory_bytes: 256
#![allow(non_snake_case)]
use std::io::*;
use std::str::FromStr;


fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
    .bytes()
    .map(|c| c.expect("failed to read char") as char)
    .skip_while(|c| c.is_whitespace())
    .take_while(|c| !c.is_whitespace())
    .collect();
    token.parse().ok().expect("failed to parse token")
}

/*
6 1000000000
695 343 933 872 827 350
*/
fn main() {
    let n: usize = read();
    let k: i64 = read();
    let a: Vec<usize> = (0..n).map(|_| read()).collect();
    let max = *a.iter().max().unwrap();
    let mut left = 0;
    let mut right = max;
    if k == 0 {
        let mut ans = *a.iter().max().unwrap();
        println!("{}", ans);
        return;
    }
    while left < right -1 {
        let findLength = (left + right) / 2;
        let mut cut = 0;
        for &i in a.iter() {
            cut += ((i as f64) / (findLength as f64)).ceil() as i64 - 1;
        }
        if cut > k {
            left = findLength;
        } else {
            right = findLength;
        }
    }
    print!("{}", right);
}


Measured memory_bytes: 3904
/* aoj1350  */
//提出用
#include<stdio.h>
#include <stdlib.h>  // qsort
#define N 500  //島の数の最大
#define M 50000 //橋の数の最大

int mst[M]={0};  //最初に作った最小木の橋を記憶する
int flag=0;      //最小木が1度作られたかどうか
int rm = -1;   //取り除いた橋の番号(初期値-1)

//橋を定義
typedef struct bridge{  
    //始点の島,終点の島,コスト
    int s; int d; int c;
}bridge_t;

//比較関数(qsort用)
int cmp(const void *a,const void *b){
  return ((bridge_t*)a)->c - ((bridge_t*)b)->c;
}

//与えられた要素の木の根を再帰で求める関数
int u_root(int x,int number[]){
    //根
    if(number[x-1] == x)
        return x;

    //経路圧縮
    else
        return number[x-1] = u_root(number[x-1],number);
}

//xとyが同じ集合に属するか否かを根を見て判断する(同じなら1を返す)
int u_find(int x, int y, int number[]){
    return u_root(x,number) == u_root(y,number);
}

//xとyの属する集合を併合
void u_union(int x, int y, int number[]){     //x,yは島の番号(1~)を表す
    number[y-1] = x;
}

//全ての要素が同じ集合に含まれているかどうかをfindで判定する関数
int allsame(int n, int number[])
{
    int y;
    for(y=2;y<=n;y++)
            if(!u_find(1,y,number)) //一つでも同じ集合に含まれない要素があるなら0を返す
                return 0;
    return 1; //全ての要素が同じ集合に含まれていれば1を返す。
}


//クラスカル法で最小全域木を生成する関数
//異常終了(最小木が生成できなかった)の時は0を返す
int kruskal(bridge_t b[], int n, int m, int number[]){
    int i=0; //配列の添字
    int mc=0;  //最小木のコスト
    //独立した点がなくなるまで繰り返す
    while(!allsame(n,number)){
        //独立していてかつ取り除かれた橋でないならその要素の根を合成する
        if(!u_find(b[i].s,b[i].d,number) && i!=rm){
            u_union(u_root(b[i].s,number),u_root(b[i].d,number),number);
            //まだ一度も最小木が作られていないならどの橋を使ったかを記憶する
            if(!flag)
                mst[i] = 1;
            //コストを足していく
            mc += b[i].c;
        }
        i++;
        //最後まで探索して、一つでも同じ集合にない要素があれば、最小木は作れないということになる
        if(i==m)
          if(!allsame(n,number))
             return 0;
    }
    return mc;
}

int main(void){
    int n,m;        //島の数,橋の数
    bridge_t b[M];  //橋の情報
    int mc;         //最初に作った最小木のコスト
    int mc2;        //2回目以降に作る最小木のコスト
    bridge_t temp;  //橋の情報の一時記憶領域
    int number[N];  //親の番号
    int alt[M] = {0};     //オルタナティブな橋の番号(初期値は全て非オルタナティブ))
    int acost=0,abridge=0;    //オルタナティブな橋のコストの和と、オルタナティブな橋の本数の和
    int i,j;

    scanf("%d%d",&n,&m);
    //n要素で初期化(初めは全ての頂点が根)
    for(i=0;i<n;i++)
        number[i] = i+1;
    //橋の始点、終点、コストを入力
    for(i=0;i<m;i++){
        scanf("%d%d%d",&b[i].s,&b[i].d,&b[i].c);
    }
    //qsortによるソート(コストの昇順)
    qsort(b,m,sizeof(bridge_t),cmp);

    //クラスカル法を行う関数を呼び出し
    //全ての要素で最小木を作る
    mc = kruskal(b,n,m,number);
    flag=1;     //１度最小木を作成した

    //numberを初期化
    for(i=0;i<n;i++){
        number[i] = i+1;
    }
    //作った最小木の中で辺を一つだけ取り除き最小木が作れるかどうかで場合分け
    for(j=0;j<m;j++){
        //最初に作った最小木の橋ならばその橋を取り除く
        if(mst[j]){
            rm = j;   //取り除いた橋の番号を記憶
            mc2 = kruskal(b,n,m,number);    //橋を一つ取り除いて最小木を作る
            //ある橋を一つ取り除いて同じコストの最小木を作れないなら、それは不変の橋である
            if(mc < mc2 || mc2 == 0)
                alt[j]=1;
            //numberを初期化しておく
            for(i=0;i<n;i++)
                number[i] = i+1;
        }
        //オルタナティブな橋が見つかれば
        if(alt[j]){
            abridge++;
            acost += b[j].c;
        }
    }
    printf("%d %d\n",abridge,acost);
    
    return 0;
}


Measured memory_bytes: 3020
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
const ll mod=1000000007;
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
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 (a>b) { a=b; return 1; } return 0; }
template <typename T>
struct ST{
  using F = function<T(T,T)>;
  int n;
  F f;
  T ti;
  vector<T> dat;
  ST(){};
  ST(F f,T ti):f(f),ti(ti){}
  void init(int n_){    
    n=1;
    while(n<n_) n<<=1;
    dat.assign(n<<1,ti);
  }
  void build(const vector<T> &v){
    int n_=v.size();
    init(n_);
    for(int i=0;i<n_;i++) dat[n+i]=v[i];
    for(int i=n-1;i;i--)
      dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
  }
  void set_val(int k,T x){
    dat[k+=n]=x;
    while(k>>=1)
      dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]);    
  }
  T query(int a,int b){
    T vl=ti,vr=ti;
    for(int l=a+n,r=b+n;l<r;l>>=1,r>>=1) {
      if(l&1) vl=f(vl,dat[l++]);
      if(r&1) vr=f(dat[--r],vr);
    }
    return f(vl,vr);
  }
};
int main(){
  int n;
  cin>>n;
  V<ll> h(n),a(n);
  for(int i=0;i<n;i++)cin>>h[i];
  for(int i=0;i<n;i++)cin>>a[i];
  auto f=[](ll a,ll b){return max(a,b);};
  ST<ll> seg(f,0);
  V<ll> dat(n+1,0);
  seg.build(dat);
  for(int i=0;i<n;i++){
      ll val=seg.query(0,h[i]);
      seg.set_val(h[i],val+a[i]);
  }
  cout<<seg.query(0,n+1)<<"\n";
}

Measured memory_bytes: 9088
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, input().split()) #整数-1map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime



class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y: return False

        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]
    
    def same(self, x, y):
        return self.find(x) == self.find(y)

N,M,K = imn()
uf = UnionFind(N)
friends_cnt = [0 for _ in range(N)]
blocks = [[] for _ in range(N)]
for i in range(M):
    a, b = imnn()
    friends_cnt[a] += 1
    friends_cnt[b] += 1
    uf.union(a, b)
for i in range(K):
    a, b = imnn()
    blocks[a].append(b)
    blocks[b].append(a)

ans = []
for i in range(N):
    num = uf.size(i)-1-friends_cnt[i]
    for b in blocks[i]:
        if uf.same(i, b): num -= 1
    ans.append(str(num))
print(' '.join(ans))



        


Measured memory_bytes: 35672
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int m[] = {0, 3, 5, 7};
int main()
{
    ll n;
    scanf("%lld", &n);
    int cnt = 0;
    for (int i = 0;; i++)
    {
        ll cur = 0;
        bool b[4] = {0};
        char buf[20];
        int l = 0, x = i;
        do
            buf[l++] = x & 3, x >>= 2;
        while (x);
        for (int j = l - 1; j >= 0; j--)
            cur = cur * 10 + m[buf[j]], b[buf[j]] = true;
        if (cur > n)
            break;
        if (!b[0] && b[1] && b[2] && b[3])
            cnt++;
    }
    printf("%d", cnt);
    return 0;
}

Measured memory_bytes: 256
import itertools
h, w=map(int, raw_input().split())
n=input()
a=list(itertools.chain(*[[c+1]*a for c, a in enumerate(map(int, raw_input().split()))]))
for i in xrange(h):
	for j in xrange(w):
		print a[i*w+j if i%2==0 else (i+1)*w-j-1],
	print

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

int main() {
  int ans = 0;
  string s,t;
  cin >> s >> t;
  if(s[0] == t[0])ans++;
  if(s[1] == t[1])ans++;
  if(s[2] == t[2])ans++;
  cout << ans;
}

Measured memory_bytes: 3588