akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
string s,str;
deque<char> ss;
int main() {
    cin >> s;
    for(int i=0;i<s.size();++i) {
        ss.push_back(s[i]);
        if(s[i]=='x')continue;
        str.push_back(s[i]);

    }

    for(int i=0;i<str.size();++i) {
        if(str[i]!=str[str.size()-i-1])  {
            cout << -1 << endl; return 0;
        }
    }
    int cnt=0;
    while(!ss.empty()) {
        if(ss.front()==ss.back()) {
            //cout << ss.front() <<" " << ss.back() << endl;
            ss.pop_front(); if(!ss.empty())ss.pop_back();
            //cout << 11 << endl;
        }
        else if(ss.front()=='x') {
            ss.pop_front(); cnt++;
        }
        else {
            ss.pop_back(); cnt++;
        }
    }
    cout << cnt << endl;

    return 0;
}


Measured memory_bytes: 640
N = int(input())
S = sorted([int(a) for a in input().split()])
X = [1] + [0] * N

def popX(i0):
    for i in range(i0, N+1):
        if X[i]:
            X[i] -= 1
            return i
    return N+1
def addX():
    for l in L:
        for i in range(l+1, N+1):
            X[i] += 1

while S:
    a = S.pop()
    c = 1
    L = [popX(0)]
    while S and S[-1] == a:
        S.pop()
        c += 1
        L.append(popX(L[-1]))
    if L[-1] > N:
        print("No")
        break
    addX()
else:
    print("Yes")

Measured memory_bytes: 34676
import java.util.*;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int x = sc.nextInt();
		int t = sc.nextInt();
		
		double N=n;
		double X=x;
		double T=t;
		
		 double res=0.0;
		if(N<X)
			res=T;
		else
		{
			res=Math.ceil(N/X);
			res=res*T;
		}
		System.out.println((int)res);
	}

}

Measured memory_bytes: 35688
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int64_t>;

int main(){
  int N;
  vi A(200010);
  priority_queue<int> q;

  cin >> N;
  for(int i=0; i<N; i++){
    cin >> A[i];
    q.push(A[i]);
  }

  for (int i=0; i<N; i++){
    if (q.top() != A[i]){
      cout << q.top() << endl;
    } else {
      q.pop();
      cout << q.top() << endl;
      q.push(A[i]);
    }
  }
}

Measured memory_bytes: 4084
#include <iostream>
#include <map>

int N, res;
std::map<unsigned int, unsigned int> mp;

int main() {
    std::cin >> N;
    for (int i=0; i<N; i++) {
        unsigned int a;
        std::cin >> a;
        if (mp.find( a ) == mp.end()) {
            mp[a] = 1;
        } else {
            if (mp[a] >= a) {
                ++res;
            }
            ++mp[a];
        }
    }
    std::map<unsigned int, unsigned int>::iterator itr=mp.begin();
    while (itr != mp.end()) {
        if (itr->second < itr->first) res += itr->second;
        ++itr;
    }

    std::cout << res << std::endl;
    return 0;
}



Measured memory_bytes: 4736
class UnionFind:
    def __init__(self, V):
        self.group = [i for i in range(V)]
        self.rank = [0] * V

    def find(self, x):
        if x != self.group[x]:
            self.group[x] = self.find(self.group[x])
        return self.group[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return
        
        if self.rank[x] < self.rank[y]:
            self.group[x] = y
        else:
            self.group[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def is_same_group(self, x, y):
        return self.find(x) == self.find(y)

class Edge:
    def __init__(self, FROM, TO, WEIGHT):
        self.FROM = FROM
        self.TO = TO
        self.WEIGHT = WEIGHT

    def __lt__(self, arg):
        return self.WEIGHT < arg.WEIGHT

V, E = map(int, input().split())

UF = UnionFind(V)

G = []
for _ in range(E):
    s, t, w = map(int, input().split())
    G.append(Edge(s, t, w))
G = sorted(G)

ans = 0
for i in range(E):
    if UF.is_same_group(G[i].FROM, G[i].TO):
        continue
    UF.unite(G[i].FROM, G[i].TO)
    ans += G[i].WEIGHT

print(ans)



Measured memory_bytes: 33964
#include<iostream>
#include<vector>

using namespace std;

bool solve(vector<int>& data, int* ans){
  bool is=false;
  for(int i=0; i<data.size(); ++i){
    if(data[i] > 1){ is=true; break; }
  }
  if(!is) return false;
  *ans = data.size() + 1;
  return true;
}

int main(){
  int n, x, ans;
  while(1){
    cin >> n;
    if(!n) break;
    vector<int> data;
    for(int i=0; i<n; ++i){
      cin >> x;
      if(x > 0) data.push_back(x);
    }
    if(solve(data, &ans)) cout << ans << endl;
    else cout << "NA" << endl;
  }
  return 0;
}

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

#define repi(i, a, b) for(int i = (int)(a); i < (int)(b); ++i)
#define rep(i, n) repi(i, 0, n)
#define all(x) (x).begin(), (x).end()

inline void Main() {
  // code
  int n,k;string s;
  cin>>n>>k>>s;
  rep(i,n) {
    if(i+1==k) {
      cout<<(char)tolower(s.at(i));
    } else {
      cout<<s.at(i);
    }
  }
  cout<<endl;
}

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(20);
  Main();
  return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int ca(int c){
  int x = 0;
  for(int i=1; i<=c; i++){
    if(c<i) break;
    c-=i;
    x++;
  }
  return x;
}

int main(void){

  long long N;
  int c, ans = 0;

  cin >> N;

  for(long long z=2; z*z<=N; z++){
    c = 0;
    while(true){
      if(N%z==0){
        N = N / z;
        c++;
      }
      else{
        ans += ca(c);
        break;
      }
    }
  }
  if(N!=1) ans++;

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3624
#include<iostream>

using namespace std;

int main(){

  int n,b,f,r,v;
  int count[4][3][10];
  
  for(b=0; b<=3; b++){
    for(f=0; f<=2; f++){
      for(r=0; r<=9; r++){
	count[b][f][r]=0;
      }
    }
  }

  cin >> n;
  for(int i=0; i<n; i++){
    cin >> b >> f >> r >> v;

    count[b-1][f-1][r-1] += v;
  }

  for(b=0; b<=3; b++){
    for(f=0; f<=2; f++){
      for(r=0; r<=9; r++){
	cout << " " << count[b][f][r];
      }
      cout << endl;
    }
    if(b<3) cout << "####################" << endl;
  }
}

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())

void solve(){
    string S, T;
    cin >> S >> T;

    vi x(26, -1), y(26, -1);
    for (int i = 0; i < (int)S.size(); i++) {
        int a = S[i] - 'a';
        int b = T[i] - 'a';
        if (x[a] != -1 || y[b] != -1){
            if (x[a] != b || y[b] != a) {
                cout << "No" << endl;
                return;
            }
        }else{
            x[a] = b;
            y[b] = a;
        }
    }

    cout << "Yes" << endl;

    return;
}

int main(int argc, char const* argv[])
{
    solve();
    return 0;
}


Measured memory_bytes: 776
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
const int INF (1<<30);

int main() {
  int N, K;
  cin >> N >> K;
  int R, S, P;
  cin >> R >> S >> P;
  string T;
  cin >> T;

  auto getPoint = [&](char c) {
    if (c == 'r') return P;
    else if (c == 's') return R;
    else return S;
  };

  int ans = 0;
  rep(mod, K) {

    int cntSame = 0;
    ans += getPoint(T[mod]);

    for (int i = mod+K; i < N; i += K) {
      if (T[i] == T[i-K]) {
        cntSame++;
        if (cntSame%2 == 0) {
          ans += getPoint(T[i]);
        }
      } else {
        cntSame = 0;
        ans += getPoint(T[i]);
      }
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <iomanip>
#include <set>
#include <ctime>
#include <tuple>
#include <bitset>
#include <assert.h>
#include <deque>
#include <functional>
using namespace std;
typedef long long ll;

#define fi first
#define se second
#define rep(i, n) for (ll i = 0; i < n; i++)
#define debugA cerr << "AAAAA" << endl
#define debug_ cerr << "-------------" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define debug_vec(v)                   \
    cout << #v << endl;                \
    for (int i = 0; i < v.size(); i++) \
    {                                  \
        cout << v[i] << " ";           \
    }                                  \
    cout << endl;
#define debug_vec2(v)                         \
    cout << #v << endl;                       \
    for (int i = 0; i < v.size(); i++)        \
    {                                         \
        for (int j = 0; j < v[i].size(); j++) \
        {                                     \
            cout << v[i][j] << " ";           \
        }                                     \
        cout << endl;                         \
    }

template <typename T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}

template <typename T>
bool chmin(T &a, const T &b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}

using Graph = vector<vector<int>>;
using P = pair<int, int>;
using P1 = pair<int, pair<int, int>>; // クラスカル法とかで、{cost, {from, to}}的に使う。
const ll LINF = 1001002003004005006ll;
const ll INF = 1001001001;
const double pi = acos(-1);

ll ans1 = 0;

vector<int> guchoku(int d, vector<vector<int>> &s, vector<int> &c)
{
    vector<int> vec(d);
    for (int i = 0; i < d; i++)
    {
        int index = 0;
        int MAX = 0;
        for (int j = 0; j < 26; j++)
        {
            if (chmax(MAX, s[i][j]))
            {
                index = j + 1;
            }
        }
        vec[i] = index;
    }
    vector<int> last(26, 0);
    for (int i = 0; i < d; i++)
    {
        ans1 += c[vec[i] - 1] * (d - last[vec[i] - 1]);
        last[vec[i] - 1] = i + 1;
    }

    return vec;
}

int main()
{
    int d;
    cin >> d;
    vector<int> c(26);
    for (int i = 0; i < 26; i++)
    {
        cin >> c[i];
    }
    vector<vector<int>> s(d, vector<int>(26));
    for (int i = 0; i < d; i++)
    {
        for (int j = 0; j < 26; j++)
        {
            cin >> s[i][j];
        }
    }
    // 愚直解
    vector<int> vec1 = guchoku(d, s, c);

    for (int i = 0; i < d; i++)
    {
        cout << vec1[i] << endl;
    }

    return 0;
}

Measured memory_bytes: 3684
#include<bits/stdc++.h>
using namespace std;
int main()
{
  char ch;
  cin>>ch;
  if(ch=='A')
  cout<<"T"<<endl;
  else if(ch=='T')
  cout<<"A"<<endl;
  else if(ch=='C')
  cout<<"G"<<endl;
  else if(ch=='G')
  cout<<"C"<<endl;
  
  return 0;
}

Measured memory_bytes: 256
a = input()
b = ["A", "C", "G", "T"]
c = 0
d = 0
for i in range(len(a)):
    e = False
    for j in range(len(b)):
        if a[i] == b[j]:
            e = True
            break
    if e:
        c += 1
        if c > d:
            d = c
    else:
        c = 0
print(d)


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

int digsum(long int a,long int b){
    int suma=0;
    int sumb=0;
    int max;
    while(a>0){
        suma += 1;
        a /= 10;
    }
    while(b>0){
        sumb += 1;
        b /= 10;
    }
    if(suma>=sumb){
        max = suma;
    }
    else{
        max = sumb;
    }
    return max;
};

int main(){
    long int N;
    cin>>N;
    int min=15;
    for(long int i=1;i<sqrt(N)+1;i++){
        if(N%i==0){
            long int j=N/i;
            if(digsum(i,j)<min){
                min = digsum(i,j);
            }
        }
    }
    cout<<min<<endl;
}

Measured memory_bytes: 3672
#include<bits/stdc++.h>
using namespace std;
typedef long long unsigned int ll;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i, start, end) for(int i = start; i < (int)(end); ++i)
int p[100000];
int idx[100000];
int main(){
    int n;
    cin >> n;
    rep(i,0,n) cin >> p[i];
    rep(i,0,n) --p[i];
    rep(i,0,n) idx[p[i]] = i;
    set<int> s;
    ll ans = 0;
    for(int x = n - 1; 0 <= x; x--){
        s.insert(idx[x]);
        ll c = 0;
        vector<int> l(2,-1);
        vector<int> r(2,n);
        {
            auto it = s.find(idx[x]);
            rep(i,0,2){
                if(it == s.begin()) break;
                it--;
                l[i] = *it;
            }
        }
        {
            auto it = s.find(idx[x]);
            rep(i,0,2){
                it++;
                if(it == s.end()) break;
                r[i] = *it;
            }
        }
        vector<int> ls(2);
        ls[0] = idx[x] - l[0]; ls[1] = l[0] - l[1];
        vector<int> rs(2);
        rs[0] = r[0] - idx[x]; rs[1] = r[1] - r[0];
        c = (ll)ls[0]*rs[1] + (ll)ls[1]*rs[0];
        ans += c * (x+1);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 5760
#include <iostream>
using namespace std;
int main() {
  string s;
  cin >> s;
  int x = 0;
  for (unsigned int i = 0; i < s.size(); ++i) {
    x += s.at(i) - '0';
    x %= 9;
  }
  if (x == 0) puts("Yes");
  else puts("No");
  return 0;
}


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

int main(){

  int N,cnt = 0;
  int A[200];

  cin >> N;
  for(int i = 0; i < N; i++){
    cin>>A[i];
  }

  for(;;){
    for(int i =0; i < N; i++){
      if(A[i]%2 == 0){
        A[i] = A[i]/2;
      }
      else{
        cout << cnt << endl;
        return 0;
      }
    }
    cnt++;
  }

  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int A,B,C,D,E,F;
	scanf("%d %d %d %d",&A,&B,&C,&D);
	E=A*B;
	F=C*D;
	if(E<F)
		printf("%d",F);
		else
			printf("%d",E);
			return 0;
}



Measured memory_bytes: 128
#include <bits/stdc++.h>
#include<math.h>
#include<algorithm> 
#define rep(i,n) for (int i = 0; i < (n) ; ++i)
using namespace std;
using ll = long long ;
using P = pair<int, int> ;
#define PI 3.14159265358979323846264338327950
#define INF 1e18
#define mod 1000000007

int main() {
    ll a, b, c, d ;
    cin >> a >> b >> c >> d ;
    ll ans = a * c ;
    ans = max(ans, a * d) ;
    ans = max(ans, b * c) ;
    ans = max(ans, b * d) ;
    cout << ans << endl ;
} 

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    while (cin >> n, n) {
        int p, d1, d2, mp, md = 0;
        for (int i=0; i<n; ++i) {
            cin >> p >> d1 >> d2;
            if (md < d1 + d2) {
                mp = p;
                md = d1 + d2;
            }
        }
        cout << mp << " " << md << endl;
    }
    return 0;
}

Measured memory_bytes: 1196
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <stack>
using namespace std;
typedef long long int ll;

int h,w,n;
int x,y;

void no(){
	cout << "NO" << endl;
}

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cin >> h >> w >> n;
	int sx,sy; cin >> sx >> sy;
	sx--; sy--;
	string s,t; cin >> s >> t;
	// top
	x=sx,y=sy;
	swap(x,y);
	for(int i=0;i<n;i++){
		if(s[i]=='U')y--;
		if(y<0){
			no();
			return 0;
		}
		if(t[i]=='D')y++;
		if(y>h-1)y=h-1;
	}
	x=sx,y=sy;
	swap(x,y);
	for(int i=0;i<n;i++){
		if(s[i]=='D')y++;
		if(y>h-1){
			no();
			return 0;
		}
		if(t[i]=='U')y--;
		if(y<0)y=0;
	}

	x=sx,y=sy;
	swap(x,y);
	for(int i=0;i<n;i++){
		if(s[i]=='L')x--;
		if(x<0){
			no();
			return 0;
		}
		if(t[i]=='R')x++;
		if(x>w-1)y=w-1;
	}
	x=sx,y=sy;
	swap(x,y);
	for(int i=0;i<n;i++){
		if(s[i]=='R')x++;
		if(x>w-1){
			no();
			return 0;
		}
		if(t[i]=='L')x--;
		if(x<0)x=0;
	}
	cout << "YES" << endl;
}

Measured memory_bytes: 920
import itertools

n = int(input())

V = list(map(int,input().split()))
C = list(map(int,input().split()))

cost = [v-c for v,c in zip(V,C)]

max_cost = 0

for i in range(1,n+1):
    for v in itertools.combinations(cost,i):
        m_cost = 0
        for c in v:
            m_cost = m_cost + c
        if max_cost < m_cost:
            max_cost = m_cost


print(max_cost)


Measured memory_bytes: 3064
H, W = map(int, input().split())
S = [input() for i in range(H)]
A = [[0 for j in range(W)] for i in range(H)]
pos = []
for i in range(H):
  for j in range(W):
    if S[i][j] == '#':
      pos.append([i, j])
      A[i][j] = 1
cnt = 0
while pos != []:
  n = len(pos)
  cnt += 1
  for i in range(n):
    x, y = pos[i][0], pos[i][1]
    if x > 0:
      if A[x-1][y] == 0:
        A[x-1][y] = 1
        pos.append([x-1, y])
    if x < H-1:
      if A[x+1][y] == 0:
        A[x+1][y] = 1
        pos.append([x+1, y])
    if y > 0:
      if A[x][y-1] == 0:
        A[x][y-1] = 1
        pos.append([x, y-1])
    if y < W-1:
      if A[x][y+1] == 0:
        A[x][y+1] = 1
        pos.append([x, y+1])
  pos = pos[n:]
print(cnt-1)

Measured memory_bytes: 199340
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using static System.Math;
using static System.Array;
using static AtCoder.Tool;
namespace AtCoder
{
    class AC
    {
        const int MOD = 1000000007;
        const int INF = int.MaxValue / 2;
        const long SINF = long.MaxValue / 2;
        const double EPS = 1e-8;
        static readonly int[] dx = { 0, 1, 0, -1 };
        static readonly int[] dy = { 1, 0, -1, 0 };
        //static List<List<int>> G = new List<List<int>>();
        //static List<List<Edge>>G = new List<List<Edge>>();
        //static List<Edge> E = new List<Edge>();
        
        static void Main(string[] args)
        {
            //var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            //Console.SetOut(sw);
            var cin = new Scanner();

            int N = int.Parse(Console.ReadLine());
            var input = Console.ReadLine().Split();
            for(var i = 0; i < N; i++)
            {
                Console.Write($"{input[0][i]}{input[1][i]}");
            }
            Console.WriteLine();

            //Console.Out.Flush();
        }
        struct Edge
        {
            public int from;

            public int to;
            public long dist;
            public Edge(int t, long c)
            {
                from = -1;
                to = t;
                dist = c;
            }
            public Edge(int f, int t, long c)
            {
                from = f;
                to = t;
                dist = c;
            }

        }
    }
    public class Scanner
    {
        public int[] ReadSplit()
        {
            return ConvertAll(Console.ReadLine().Split(), int.Parse);
        }
        public long[] ReadSplitL()
        {
            return ConvertAll(Console.ReadLine().Split(), long.Parse);
        }
        public double[] ReadSplitD()
        {
            return ConvertAll(Console.ReadLine().Split(), double.Parse);
        }
    }
    public static class Tool
    {
        static public void Initialize<T>(ref T[] array, T initialvalue)
        {
            for (var i = 0; i < array.Length; i++)
            {
                array[i] = initialvalue;
            }
        }
        static public void Swap<T>(ref T a, ref T b)
        {
            T keep = a;
            a = b;
            b = keep;
        }

        static public void Display<T>(T[,] array2d, int n, int m)
        {
            for (var i = 0; i < n; i++)
            {
                for (var j = 0; j < m; j++)
                {
                    Console.Write($"{array2d[i, j]} ");
                }
                Console.WriteLine();
            }
        }

    }
}


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

using namespace std;

typedef vector<int> vec;
typedef vector<vec> mat;

class Rect
{
public:
    int border[2][2];
    bool in(int x,int d)
    {
        return x>=border[d][0]&&x<=border[d][1];
    }
    void init()
    {
        for(int i=0;i<2;i++)
        {
            for(int j=0;j<2;j++)
            {
                scanf("%d",&border[i][j]);
            }
        }
    }
};

int dimension=0;
int Size=2;

class Node
{
public:
    int idx;
    vec pos;

    Node()
    {
        pos.resize(2);
    }
    bool operator < (const Node & node) const
    {
        int d=dimension;
        return pos[d]<node.pos[d];
    }
};

priority_queue<int,vector<int>,greater<int> > ans;

class KDTree
{
public:
    vector<Node> nodes;
    int n;

    KDTree(int _n)
    {
        n=_n;
        nodes.resize(n);
        init();
        build(0,n,0);
    }

    void init()
    {
        for(int i=0;i<n;i++)
        {
            scanf("%d %d",&nodes[i].pos[0],&nodes[i].pos[1]);
            nodes[i].idx=i;
        }
    }

    void build(int l,int r,int d)
    {
        if(l+1>=r) return;
        int mid=(l+r)/2;
        dimension=d;
        nth_element(nodes.begin()+l,nodes.begin()+mid,nodes.begin()+r);
        build(l,mid,d^1);
        build(mid+1,r,d^1);
    }

    void query(int l,int r,Rect & rect,int d)
    {
        if(l>=r) return;
        int mid=(l+r)/2;
        if(rect.in(nodes[mid].pos[0],0)&&rect.in(nodes[mid].pos[1],1))
        {
            ans.push(nodes[mid].idx);
        }
        if(nodes[mid].pos[d]<=rect.border[d][1])
        {
            query(mid+1,r,rect,d^1);
        }
        if(nodes[mid].pos[d]>=rect.border[d][0])
        {
            query(l,mid,rect,d^1);
        }
    }
};

int main()
{
    int n,q;

    while(scanf("%d",&n)!=EOF)
    {
        KDTree kd(n);
        scanf("%d",&q);

        while(q--)
        {
            Rect rect;
            rect.init();
            kd.query(0,n,rect,0);
            while(!ans.empty())
            {
                int top=ans.top();ans.pop();
                printf("%d\n",top);
            }
            puts("");
        }
    }

    return 0;
}



Measured memory_bytes: 33208
#include<bits/stdc++.h>
using namespace std;
#define N 100000 + 5
#define Mod 1000000007
#define rep(i, l, r) for(int i = l; i <= r; ++i)
int n, k, tot, ans, a[N], dp[N];
int read(){
    char c; int x = 0, f = 1;
    c = getchar();
    while(c > '9' || c < '0'){ if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int Inc(int a, int b){
    return (a += b) >= Mod ? a - Mod : a;
}
int Dec(int a, int b){
    return (a -= b) < 0 ? a + Mod : a;
}
int Mul(int a, int b){
    return 1ll * a * b % Mod;
}
int Qpow(int a, int b){
    int ans = 1;
    while(b){
        if(b & 1) ans = Mul(ans, a);
        a = Mul(a, a), b >>= 1;
    }
    return ans;
}
int main(){
    n = read(), k = read();
    for(int i = 1; i * i <= n; ++i) if(n % i == 0){
        a[++tot] = i;
        if(n / i != i) a[++tot] = n / i;
    }
    sort(a + 1, a + tot + 1);
    rep(i, 1, tot){
        dp[i] = Qpow(k, (a[i] + 1) / 2);
        rep(j, 1, i - 1) if(a[i] % a[j] == 0) dp[i] = Dec(dp[i], dp[j]);
        if(a[i] & 1) ans = Inc(ans, Mul(dp[i], a[i]));
        else ans = Inc(ans, Mul(dp[i], a[i] / 2));
    }
    printf("%d", ans);
    return 0;
}

Measured memory_bytes: 3744
#include <cstdio>
    #include <algorithm>
    using namespace std;
     
    int N;
    int Ai[300000];
    int V1[300000], V2[300000];
    int W1[300000], W2[300000];
    int G[300000][20];
    int GL[300000];
    int n2;
    int res[300000];
    int deg[300000];
     
    void solve()
    {
    	int i, j, k;
    	n2 = (1<<N);
    	int v;
    	for(i=0; i<n2; i++){
    		for(j=0; j<N; j++){
    			v = (i | (1<<j));
    			if(v != i){
    				G[i][GL[i]] = v;
    				GL[i] ++;
    			}
    		}
    	}
    	for(i=0; i<n2; i++){
    		for(j=0; j<GL[i]; j++){
    			deg[G[i][j]] ++;
    		}
    	}
    	for(i=0; i<n2; i++){
    		V1[i] = Ai[i];
    		W1[i] = i;
    	}
    	int top = -1;
    	for(i=0; i<n2; i++){
    		if(deg[i] == 0){
    			deg[i] = top;
    			top = i;
    		}
    	}
    	while(top != -1){
    		int u = top;
    		top = deg[top];
    		for(i=0; i<GL[u]; i++){
    			v = G[u][i];
    			int t[4];
    			int tw[4];
    			t[0] = V1[u];
    			t[1] = V2[u];
    			t[2] = V1[v];
    			t[3] = V2[v];
    			tw[0] = W1[u];
    			tw[1] = W2[u];
    			tw[2] = W1[v];
    			tw[3] = W2[v];
    			
    			int mx2=0, mxi2;
				for(j=0; j<4; j++){
					if(t[j] > mx2){
						mx2 = t[j];
						mxi2 = j;
					}
    			}
    			V1[v] = t[mxi2];
    			W1[v] = tw[mxi2];
    			mx2 = 0;
    			for(j=0; j<4; j++){
    				if(tw[j] != W1[v]){
    					if(t[j] > mx2){
    						mx2 = t[j];
    						mxi2 = j;
    					}
    				}
    			}
    			V2[v] = t[mxi2];
    			W2[v] = tw[mxi2];
    			    			
				//V1[v] = t[3];
    			//V2[v] = t[2];
    			deg[v] --;
    			if(deg[v] == 0){
    				deg[v] = top;
    				top = v;
    			}
    		}
    		///top = deg[top];
    	}
    	int l2 = 0;
    	int tmp, mx;
    	for(i=1; i<n2; i++){
    		mx = 0;
    		l2 = 0;
    		for(j=0; j<N; j++){
    			if( (i & (1<<j)) > 0){
    				k = l2+(1<<j)-1;
    				tmp = V1[k] + V2[k];
    				if(tmp > mx)
    					mx = tmp;
    				l2 += (1<<j);
    			}
    		}
    		tmp = V1[i] + V2[i];
    		if(tmp > mx)
    			mx = tmp;
    		res[i-1] = mx; 
    	}
    	tmp = 0;
    	for(i=0; i<n2-1; i++){
    		if(res[i] < tmp)
    			res[i] = tmp;
    		else
    			tmp = res[i];
    	}
    	for(i=0; i<n2-1; i++)
    		printf("%d\n", res[i]);
    }
     
    int main()
    {
    	//freopen("in.txt", "r", stdin);
    	int i;
    	scanf("%d", &N);
    	for(i=0; i<(1<<N); i++)
    		scanf("%d", &Ai[i]);
    	solve();
    	return 0;
    }

Measured memory_bytes: 33536
#include<bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
  
typedef pair<double,double> P;
typedef pair<P,double> P2;
  
P rot(P p, double a){
  a=a*M_PI/180.0;
  return P(p.first*cos(a)+p.second*(-sin(a)),
  p.first*sin(a)+p.second*cos(a));
}
  
double abss(P a,P b){
  return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);
}
  
double x,y,r;int tt;
vector<P>v;
int main(){
  
  int n;
  cin>>n;
  
    double ans=1e13;
      
    v.clear();
    
    r(i,n){
      cin>>x>>y;
      v.push_back(P(x,y));
    }
  
    r(i,1){
      sort(v.begin(),v.end());
      r(j,n){
        for(int k=j+1,c=0;k<n;k++,c++){
          if(c>50)break;
          ans=min(ans,abss(v[k],v[j]));
        }
      }
      r(j,n)v[i]=rot(v[i],0.5);
    }
  
    printf("%d\n",(int)ans);
      
}


Measured memory_bytes: 11240
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<stack>
#include<queue>
#include<string>
#include<set>
#include<map>
using namespace std;
#define rep(i,n) for(int i=0;(i)<(n);(i)++)
#define FOR(i,m,n) for(int i=(m);(i)<(n);(i)++)
typedef long long ll;

int main(){
    int n,y;
    cin >> n >> y;
    for(int i=0;i<=n;i++){
        for(int j=0;i+j<=n;j++){
            int k = n-(i+j);
            if(10000*i+5000*j+1000*k==y){
                cout << i << ' '<<j<<' '<<k<<endl;
                return 0;
            }
        }
    }
    cout << -1 <<' '<<-1<<' '<<-1<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, k;
  long long s = 0;
  cin >> n >> k;
  for (int b = k + 1; b <= n; b++) {
    s += (b - k) * (n / b) + max(0, n % b - k + (k ? 1 : 0));
  }
  cout << s;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int mtc[10] = {-1, 2, 5, 5, 4, 5, 6, 3, 7, 6};
int gcd (int a, int b) {
  if (a < b) {
    swap(a, b);
  }
  if (b == 0) {
    return 0;
  }
  while (b) {
    a %= b;
    swap(a, b);
  }
  if (a < 0) {
    a *= -1;
  }
  return a;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> a(m);
  for (int i = 0; i < m; i++) {
    cin >> a[i];
  }
  vector<int> dgt(n + 1, -1);
  dgt[0] = 0;
  for (int i = 0; i <= n; i++) {
    for (int c = 0; c < m; c++) {
      int use = mtc[a[c]];
      if (i >= use && dgt[i - use] != -1) {
        dgt[i] = max(dgt[i], dgt[i - use] + 1);
      }
    }
  }
  int crr = n;
  while (crr) {
    int maxv = -1;
    for (int c = 0; c < m; c++) {
      int num = a[c];
      int use = mtc[num];
      if (crr >= use && dgt[crr - use] == dgt[crr] - 1) {
        maxv = max(maxv, num);
      }
    }
    cout << maxv;
    crr -= mtc[maxv];
  }
  return 0;
}

Measured memory_bytes: 256
S = input()
rS = S[::-1]
keys = ['dream', 'dreamer', 'erase', 'eraser']
reversed_keys = [keys[i][::-1] for i in range(len(keys))]
i = 0

while i < len(rS):
    if rS[i:i+5] in reversed_keys:
        i += 5
    elif rS[i:i+6] in reversed_keys:
        i += 6
    elif rS[i:i+7] in reversed_keys:
        i += 7
    else:
        break
if i == len(rS):
    print('YES')
else:
    print('NO')


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
int main() {
	int n; cin >> n;
	string s; cin >> s;
	int l[26], r[26];
	int ans = 0;
	int cnt = 0;
	for(int i=0;i<26;i++){
		l[i] = 0;
		r[i] = 0;
	}
	for(int i=0;i<n-1;i++){
		for(int j=0;j<=i;j++){
			l[s[j]-'a']++;
			for(int k=i+1;k<n;k++){
				r[s[k]-'a']++;
			}
		}
		for(int j=0;j<26;j++){
			if(l[j]>0 && r[j]>0){
				cnt++;
			}
		}
		ans = max(ans, cnt);
		for(int j=0;j<26;j++){
			l[j] = 0;
			r[j] = 0;
		}
		cnt = 0;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
// Space O(C), Time O(NC)
#include <iostream>
#include <vector>

using namespace std;
int n, c;

int main() {
    scanf("%d %d", &n, &c);
    vector<int> w(n), v(n);
    for (int i = 0; i < n; ++i) {
        scanf("%d %d", &w[i], &v[i]);
    }

    // dp[i][j] := maximum total value of a subset of the first i items, with total size at most j
    vector<long long> dp(c + 1, 0);
    for (int j = 0; j <= c; ++j) {
        dp[j] = 0;
    }

    for (int i = 1; i <= n; ++i) {
        vector<long long> cur(c + 1, 0);
        for (int j = 0; j <= c; ++j) {
            if (j < w[i - 1]) cur[j] = dp[j];
            else cur[j] = max(dp[j], dp[j - w[i - 1]] + v[i - 1]);
        }
        dp = cur;
    }
    printf("%lld\n", dp[c]);
    return 0;
}

Measured memory_bytes: 4840
#include <iostream>
#include<iomanip>
#include <map>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <queue>
#define INF 1e9+7
#define rep(i,n) for(ll i=0;i<n;i++)
#define NO cout<<"NO"<<endl;
#define YES cout<< "YES"<<endl;
#define No cout<< "No"<<endl;
#define Yes cout<< "Yes"<<endl;
#define all(a) a.begin(),a.end()
#define P pair<int,int>
#define space ' '
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

//(int)'a'=97 (int)'A'=65 (int)'1'=49
//おまじない

const int maxn = 300000;

int main(){
    
    ll n;
    ll mod = INF;
    ll ans=0;
    ll a[maxn];
    cin >> n;
    
    rep(i,n)cin >> a[i];
    
    ll b = 1;
    rep(i,60){
        ll c = b;
        b=(b<<1);
        ll A=0;
        rep(j,n){
            if(c<=a[j]%b)A++;
        }
        c = c%mod;
        ans += (((A*(n-A))%mod)*c)%mod;
        ans %=mod;
    }
    
    cout << ans <<endl;
    
    return 0;
}


Measured memory_bytes: 2560
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    s = list(input())
    if s[2]==s[3] and s[4]==s[5]:
      print("Yes")
    else:
      print("No")
    
    return

#Solve
if __name__ == "__main__":
    solve()


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

int main (){
    int a, b;
    cin>>a>>b;
    if(a%3==0||b%3==0||(a+b)%3==0){
        cout<<"Possible"<<endl;
    }
    else{
        cout<<"Impossible"<<endl;
    }
}
    

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#define rep(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define N 10

void mpAdd(int *,int *,int *);
void mpNum2Str(char *,int *);
void mpStr2Num(int *,char *);

int main(void){
  int ans[1000],a[1000],b[1000],i,j,n;
  char ach[1000],bch[1000],str[1000];

  scanf("%d",&n);
  
  rep(j,n){
    scanf("%s",ach);
    scanf("%s",bch);    
    mpStr2Num(a,ach);
    mpStr2Num(b,bch);
    mpAdd(ans,a,b);
    mpNum2Str(str,ans);
    
    if(strlen(str)>80)printf("overflow\n");
    else printf("%s\n",str);
  }
  return 0;
}

void mpAdd(int *ret, int *a, int *b){
    int  i;
    int  lr, la, lb;
    int  *rr;
    int  x;

    la = *a;
    lb = *b;
    lr = (la >= lb) ? la : lb;

    rr = ret;
    x = 0;
    for (i = 1; i <= lr; i++) {
        if (i <= la) x += *++a;
        if (i <= lb) x += *++b;
        if (x < N) {
            *++rr = x;
            x = 0;
        } else {
            *++rr = x - N;
            x = 1;
        }
    }
    *++rr = x;
    *ret = lr + x;
}

void mpNum2Str(char *str, int *num){
    int  i, j;
    char *ss;
    int  x;

    if (*num == 0) {
        *str++ = '0';
        *str = '\0';
        return;
    }

    ss = str - 1;
    for (i = *num; i > 0; i--) {
        x = *++num;
        for (j = 1; j < N; j *= 10) {
            *++ss = x % 10 + '0';
            x /= 10;
        }
    }
    while (*ss == '0') ss--;

    *(ss + 1) = '\0';    
    while (str < ss) {
        x = *str;
        *str++ = *ss;
        *ss-- = x;
    }
}

void mpStr2Num(int *num, char *str){
    char *ss;
    int  *nn;
    int  k;
    int  x;

    while (*str == ' ' || *str == '\t') str++;
    while (*str == '0') str++;
    ss = str;
    while (*ss >= '0' && *ss <= '9') ss++;

    if (ss == str) {
        *num = 0;
        return;
    }

    x = 0;
    k = 1;
    nn = num;
    do {
        x += (*--ss - '0') * k;
        k *= 10;
        if (k == N || ss == str) {
            *++nn = x;
            x = 0;
            k = 1;
        }
    } while (ss != str);

    *num = nn - num;
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>

int main() {
    int h, w, n, a, pos = 0;
    std::cin >> h >> w >> n;
    std::vector<int> ls(h * w);
    for (auto i = 1; i <= n; i++) {
        std::cin >> a;
        for (; a--; ) ls[pos++] = i;
    }
    for (auto i = 0; i < h / 2; i++) {
        for (auto j = 0; j < w - 1; j++) {
            std::cout << ls[2 * i * w + j] << " ";
        }
        std::cout << ls[2 * i * w + w - 1] << std::endl;
        for (auto j = 0; j < w - 1; j++) {
            std::cout << ls[(2 * i + 2) * w - 1 - j] << " ";
        }
        std::cout << ls[(2 * i + 2) * w - w] << std::endl;
    }

    if (h % 2) {
        for (auto j = 0; j < w - 1; j++) {
            std::cout << ls[(h - 1) * w + j] << " ";
        }
        std::cout << ls[(h - 1) * w + w - 1] << std::endl;
    }

    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e3 + 5;
ll f[N][N];
pair<int, int> p[N];
ll cal(int cnt, int l, int r) {
    if(l > r) return 0;
    if(~f[l][r]) return f[l][r];
    ll ans = 1LL * p[cnt].first * abs(p[cnt].second - l) + cal(cnt + 1, l + 1, r);
    ans = max(ans, 1LL * p[cnt].first * abs(p[cnt].second - r) + cal(cnt + 1, l, r - 1));
    return f[l][r] = ans;
}
int main() {
    int n;
    scanf("%d", &n);
    for(int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        p[i] = {x, i};
    }
    sort(p + 1, p + n + 1,[](pair<int, int> a, pair<int, int> b) {
        return a.first > b.first;
    });
    memset(f, -1, sizeof f);
    printf("%lld\n", cal(1, 1, n));
    return 0;
}

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

#define DUMP(x) cerr << #x << "=" << x << endl
#define DUMP2(x, y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<")"<< endl
#define BINARY(x) static_cast<bitset<16> >(x)

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for (int i=m;i<(int)(n);i++)

#define in_range(x, y, w, h) (0<=(int)(x) && (int)(x)<(int)(w) && 0<=(int)(y) && (int)(y)<(int)(h))
#define ALL(a) (a).begin(),(a).end()

typedef long long ll;
const int INF   = 1e9;
const ll  INFLL = 1e18;
typedef pair<int, int> PII;
int dx[4]={0, -1, 1, 0}, dy[4]={-1, 0, 0, 1};

bool dp[51][2501][2501];

int main()
{
    ios::sync_with_stdio(false);

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

    vector<int> sum(N+1);
    rep(i, N) sum[i+1] = sum[i] + T[i];

    dp[0][0][0] = true;

    rep(n, N) rep(t1, 2501) rep(t2, 2501) {
        if (!dp[n][t1][t2]) continue;
        dp[n+1][t1+T[n]][t2] = true;
        dp[n+1][t1][t2+T[n]] = true;
        dp[n+1][t1][t2] = true;
    }

    int ans = INF;
    rep(t1, 2501) rep(t2, 2501) {
        if (!dp[N][t1][t2]) continue;
        int t3 = sum[N] - (t1 + t2);
        ans = min(ans, max({t1, t2, t3})); 
    }
    cout << ans << endl;
}

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

#define copy(from, to) copy(from.begin(), from.end(), back_inserter(to));
#define sort(a) sort(a.begin(), a.end())

typedef long long ll;
using namespace std;

template<class T>
void load(vector<T> &v, int n) {
  for (int i = 0; i < n; ++i) {
    T t;
    cin >> t;
    v.push_back(t);
  }
}

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

  cout << (k / 2) * (k - k / 2) << endl;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpPractice
{
	class Program
	{
		static bool IsRightTriangle(int a, int b, int c)
		{
			return a * a + b * b == c * c;
		}
		static void Main(string[] args)
		{
			int n = int.Parse(Console.ReadLine());
			for (int j = 0; j < n; j++)
			{
				List<int> list = new List<int>();
				foreach (string val in Console.ReadLine().Split(' '))
				{
					list.Add(int.Parse(val));
				}
				bool flg = false;
				for (int i = 0; i < 3; i++)
				{
					flg |= IsRightTriangle(list[i], list[(i + 1) % 3], list[(i + 2) % 3]);
				}
				Console.WriteLine(flg ? "YES" : "NO");
			}
		}
	}
}

Measured memory_bytes: 5472
d,g= map(int, input().split())
p= [list(map(int, input().split())) for i in range(d)]
ans=10**9+7

for i in range(2**d):
    q=[0]*d
    cnt=0
    count=0
    for j in range(d):
        if (i>>j)&1:
            cnt+=p[j][0]*((j+1)*100)+p[j][1]
            count+=p[j][0]
            q[j]=1
    if cnt>=g:
        ans=min(count,ans)
    else:
        for k in range(d):
            if q[d-1-k]==0:
                v=-((g - cnt) // -((d-k) * 100))
                if v<p[d-1-k][0]:
                    ans=min(count+v,ans)
                    break
                else:
                    break

print(ans)

Measured memory_bytes: 41584
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
#define LL long long
vector<int>G[MAXN];
int N;
vector<int>dep[MAXN];
bool vis[MAXN];
int maxdepth;
int depth[MAXN],fa[MAXN],cost[MAXN];
int sumcost[MAXN][20],anc[MAXN][20];
int order[MAXN];
queue<int>q;

void bfs() {
    memset(vis,false,sizeof(vis));
    while (!q.empty()) q.pop();
    q.push(1);
    fa[0] = -1;
    depth[1] = 0;
    cost[1] = 0;
    maxdepth = 0;
    vis[1] = true;
    dep[0].push_back(1);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = 0 ; i < (int)G[u].size() ; i++) {
            int v = G[u][i];
            if (vis[v]) continue;
            vis[v] = true;
            cost[v] = 1;
            depth[v] = depth[u] + 1;
            maxdepth = max(maxdepth,depth[u] + 1);
            dep[depth[v]].push_back(v);
            fa[v] = u;
            q.push(v);
        }
    }
}

void preprocess()
{
    memset(sumcost,0,sizeof(sumcost));
    for (int i = 1 ; i <= N ; i++)
    {
        anc[i][0] = fa[i];
        sumcost[i][0] = cost[i];
        for (int j = 1 ; (1 << j) <= N ; j++) anc[i][j] = -1;
    }
    for (int j = 1 ; (1 << j) <= N ; j++)
    {
        for (int i = 1 ; i <= N ; i++)
        {
            if (anc[i][j - 1] != -1)
            {
                int a = anc[i][j - 1];
                anc[i][j] = anc[a][j - 1];
                sumcost[i][j] = sumcost[i][j - 1] + sumcost[a][j - 1];
            }
        }
    }
}

int query(int p,int q)
{
    int tmp,log;
    if (depth[p] < depth[q]) swap(p,q);
    for (log = 1 ; (1 << log) <= depth[p] ; log++); log--;
    int ans = 0;
    for (int i = log ; i >= 0 ; i--)
    {
        if (depth[p] - (1 << i) >= depth[q])
        {
            ans += sumcost[p][i];
            p = anc[p][i];
        }
    }
    if (p == q) return ans;
    for (int i = log ; i >= 0 ; i--)
    {
        if (anc[p][i] != -1 && anc[p][i] != anc[q][i])
        {
            ans += sumcost[p][i]; p = anc[p][i];
            ans += sumcost[q][i]; q = anc[q][i];
        }
    }
    ans += cost[p];
    ans += cost[q];
    return ans;
}


int main() {
    scanf("%d",&N);
    for (int i = 2 ; i <= N ; i++) {
        int x;
        scanf("%d",&x);
        G[x].push_back(i);
    }
    bfs();
    for (int i = 0 ; i <= maxdepth ; i++) sort(dep[i].begin(),dep[i].end());
    int cnt = 0;
    order[cnt++] = 1;
    preprocess();
    memset(vis,false,sizeof(vis));  while (!q.empty()) q.pop();
    vis[1] = true;
    q.push(1);
    for (int i = 0 ; i < (int)dep[1].size() ; i++) {q.push(dep[1][i]);}
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = 0 ; i < (int)G[u].size() ; i++) {
            int v = G[u][i];
            if (vis[v]) continue;
            vis[v] = true;
            order[cnt++] = v;
            q.push(v);
        }
    }
   // for (int i = 0 ; i < cnt ; i++) printf("%d ",order[i]); puts("");
    LL ans = 0;
    for (int i = 1 ; i < cnt ; i++) ans += query(order[i - 1],order[i]);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 31360
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <math.h>

using namespace std;

typedef long long int ll;
typedef long double ld;

#define rep(i,n) for(int i = 0; i < (n); ++i)
#define vsort(a) sort(a.begin(), a.end())
#define rev(a) reverse(a.begin(), a.end())


// a,bの最小公倍数
ll LCM(ll a, ll b){ll lcm = a * b; ll r = a % b;while(r != 0){a = b; b = r; r = a % b;}return lcm /= b;}
// a,bの最大公約数
ll GCD(ll a, ll b){ll r = a % b;while(r != 0){a = b; b = r; r = a % b;}return b;}


const int MOD = 1000000007;
const int INF = INT_MAX;



int main(){

    int n;
    cin >> n;
    int a[n];
    rep(i,n) cin >> a[i];

    int flag = 1;
    rep(i,n){
        if (a[i]%2 == 0){
            if (a[i]%3 == 0 || a[i]%5 == 0) ;
            else flag = 0;
        }
    }

    if (flag) cout << "APPROVED" << endl;
    else cout << "DENIED" << endl;

}





//              g++ -std=c++1z


Measured memory_bytes: 888
N = gets.chomp.to_i
A = gets.split(" ").map!{|i|i.to_i}
cnt = 0
for i in 0..(N-2)
    if A[i] != (i+1)
        cnt += 1
    end
end
if cnt > 2
    puts "NO"
else 
    puts "YES"
end


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

#define println(msg) cout << msg << endl
#define yes_or_no(flag) if (flag) { println("Yes"); } else { println("No"); }
#define sort_vec(vec) sort(vec.begin(), vec.end())
#define rsort_vec(vec) sort(vec.rbegin(), vec.rend()) // greater<int>()

int main() {
  // 入力
  int N, K;
  cin >> N >> K;

  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
  }
  
  // 計算
  map<int, int> ret;
  
  for (auto a : A) {
    if (ret.count(a)) {
      ret[a]++;
    } else {
      ret[a] = 1;
    }
  }
  
  int key_num = ret.size();
  int num = key_num - K; // 何キー削除すれば良いか
  
  multimap<int, int> r;
  
  for (auto x : ret) {
    r.emplace(pair<int, int>{ x.second, x.first });
  }
  
  int z = 0;
  for (auto x : r) {
    if (num <= 0) {
      break;
    }
    z += x.first;
    num--;
  }
    
  // 出力
  println(z);
}

Measured memory_bytes: 22564
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define outy printf("Yes\n")
#define outn printf("No\n")
#define outf printf("First\n")
#define outs printf("Second\n")
#define FOR(a,b,c) for(int a=b;a<=c;a++)
#define FORD(a,b,c) for(int a=b;a>=c;a--)
#define FORL(a,b) for(int a=head[b];a;a=nxt[a])
#define in(a)  a=read()
#define in2(a,b)  a=read(),b=read()
#define in3(a,b,c)  a=read(),b=read(),c=read()
#define in4(a,b,c,d)  a=read(),b=read(),c=read(),d=read()
#define inl(a)  a=readl()
#define inl2(a,b)  a=readl(),b=readl()
#define inl3(a,b,c)  a=readl(),b=readl(),c=readl()
#define inl4(a,b,c,d)  a=readl(),b=readl(),c=readl(),d=readl()
#define out(a) printf("%d\n",a)
#define out2(a,b) printf("%d %d\n",a,b)
#define out3(a,b,c) printf("%d %d %d\n",a,b,c)
#define out4(a,b,c,d) printf("%d %d %d %d\n",a,b,c,d)
#define outl(a) printf("%lld\n",a)
#define outl2(a,b) printf("%lld %lld\n",a,b)
#define outl3(a,b,c) printf("%lld %lld %lld\n",a,b,c)
#define outl4(a,b,c,d) printf("%lld %lld %lld %lld\n",a,b,c,d)
#define clr(x) memset(x,0,sizeof(x))
inline int read(){
    char c;int s=0,t=1;
    while(!isdigit(c=getchar()))if(c=='-')t=-1;
    do{s=s*10+c-'0';}while(isdigit(c=getchar()));
    return s*t;
}
inline ll readl(){
    char c;ll s=0;int t=1;
    while(!isdigit(c=getchar()))if(c=='-')t=-1;
    do{s=s*10+c-'0';}while(isdigit(c=getchar()));
    return s*t;
}
/*------------------------------------------------------------*/
#define mod 1000000007
#define maxn 1
/*------------------------------------------------------------*/
int f[100010];
int ans=0;
int main(){
	int n;
	in(n);
	FOR(i,1,n){
		int c;
		in(c);
		f[c-1]++;
		ans=max(ans,f[c-1]);
		f[c+1]++;
		ans=max(ans,f[c+1]);
		f[c]++;
		ans=max(ans,f[c]);
	}
	out(ans);
}

Measured memory_bytes: 640