akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
static const int MAX = 100000;
static const int NIL = -1;

int n;
vector<int> G[MAX];
int color[MAX];

void dfs(int r, int c) {
  stack<int> S;
  S.push(r);
  color[r] = c;
  while (!S.empty()) {
    int u = S.top(); S.pop();
    for (int i = 0; i < G[u].size(); i++) {
      int v = G[u][i];
      if (color[v] == NIL) {
        S.push(v);
        color[v] = c;
      }
    }
  }
}

void assignColor() {
  int id = 1;
  for (int i = 0; i < n; i++) {
    color[i] = NIL;
  }
  for (int i = 0; i < n; i++) {
    if (color[i] == NIL) {
      dfs(i, id++);
    }
  }
}

int main() {
  int m, u, v, q;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }

  assignColor();

  cin >> q;
  for (int i = 0; i < q; i++) {
    cin >> u >> v;
    if (color[u] == color[v]) {
      cout << "yes" << endl;
    } else {
      cout << "no" << endl;
    }
  }

  return 0;
}

Measured memory_bytes: 8944
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please


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


	ll X, Y;
	cin >> X >> Y;

	if (X % Y == 0) co(-1);
	else co(X);

	Would you please return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <utility>
#include <stack>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <climits>
#include <set>
#include <cmath>
using namespace std;

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

    vector <long long> divisors;
    for(int i = 1; i < int(sqrt(M)) + 1; i++){
        if(M % (long long) i == 0){
            divisors.push_back(i);
            divisors.push_back(M / (long long) i);
        }
    }
    sort(divisors.begin(), divisors.end());
    for(int i = divisors.size() - 1; i >= 0; i--){
        if(M / divisors[i] >= N){
            cout << divisors[i] << endl;
            break;
        }
    }
}


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

int main() {
    deque<char> s;
    int q;
    string ss;
    cin>>ss>>q;
    for (char c:ss)
        s.push_back(c);
    int f=0;
    for (int i=0;i<q;i++) {
        int t;cin>>t;
        if (t==1)
            f=1-f;
        else {
            int a;char b;cin>>a>>b;
            if (f)
                a=3-a;
            if (a==1)
                s.push_front(b);
            else
                s.push_back(b);
        }
    }
    if (f)
        reverse(s.begin(),s.end());
    for (char c:s)
        cout<<c;
    cout<<endl;
    return 0;
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
using P = pair<lint, lint>;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
constexpr int MOD = 1000000007;
constexpr int INF = 2147483647;
void yes(bool expr) {
  cout << (expr ? "Yes" : "No") << "\n";
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  lint W, H;
  cin >> W >> H;
  vector<lint> p(W);
  REP(i, W) cin >> p[i];
  vector<lint> q(H);
  REP(i, H) cin >> q[i];
  vector<P> s;
  REP(i, W) s.push_back(make_pair(p[i], 0));
  REP(i, H) s.push_back(make_pair(q[i], 1));
  sort(ALL(s), [](auto const &a, auto const &b) { return a.first < b.first; });
  lint ans = 0;
  lint zeros = 0;
  lint ones = 0;
  REP(i, W+H) {
    if(s[i].second == 0) {
      ans += s[i].first * (H-ones + 1);
      zeros++;
    } else {
      ans += s[i].first * (W-zeros + 1);
      ones++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 8048
object Scanner {
  private val buf = new Array[Byte](1024); private var ptr = 0; private var len = 0
  @inline private def isPrintableChar(c: Int): Boolean = 33 <= c && c <= 126
  @inline private def hasNextByte(): Boolean =
    if (ptr >= len) { ptr = 0; len = System.in.read(buf); len > 0 } else { true }
  @inline private def hasNext(): Boolean = {
    while (hasNextByte() && !isPrintableChar(buf(ptr))) ptr += 1
    hasNextByte()
  }
  @inline private def readByte(): Byte =
    if (hasNextByte()) { val res = buf(ptr); ptr += 1; res } else { -1 }
  def next(): String = {
    if(!hasNext()) ???
    val sb = new StringBuilder; var b = readByte()
    while (isPrintableChar(b)) { sb.append(b.toChar); b = readByte() }
    sb.toString
  }
  def nextInt(): Int = {
    val n = nextLong()
    if (n < Int.MinValue || Int.MaxValue < n) ???
    n.toInt
  }
  def nextLong(): Long = {
    if(!hasNext()) ???
    var minus = false; var b = readByte()
    if (b == '-') { minus = true; b = readByte() }
    def go (b: Byte, n: Long = 0): Long =
      if ('0' <= b && b <= '9') { go(readByte(), n * 10 + b - '0') }
      else if (minus) { -n } else { n }
    go(b)
  }
  def nextDouble(): Double = next.toDouble
}
object Main extends App {
  val n = Scanner.nextInt()
  val a = Array.fill(n)(Scanner.nextInt())
  var i = 0
  var suc = 0
  var count = 0
  while (i<n-1){
    if (a(i)==a(i+1)){
      suc = suc + 1
    } else {
      count = count + (suc+1)/2
      suc = 0
    }
    i = i + 1
  }
  count = count + (suc+1)/2
  println(count)
}

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

using namespace std;
const int maxn = 1e5+10;

int n;
int niz[maxn];
int dp[maxn];

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", niz+i);
		
	dp[0] = 0, dp[1] = abs(niz[0] - niz[1]);
	for (int i = 2; i < n; i++)
		dp[i] = min(dp[i - 2] + abs(niz[i] - niz[i - 2]), dp[i - 1] + abs(niz[i] - niz[i - 1]));
	printf("%d", dp[n - 1]);
	return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define puts(i) cout << i << endl
#define INF INT_MAX;
#define INFL LLONG_MAX;
typedef long long ll;
using namespace std;

int n;
string s;

int main(){
  int s,w;cin >> s >> w;
  if(w>=s) puts("unsafe");
  else puts("safe");
}


Measured memory_bytes: 3624
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, K = MAP()
S = input()

flg = [S[0]] #各連続部分の数字
count = []   #連続部分の個数
cnt = 1
tmp = S[0]

for x in S[1:]:
	if x == tmp:
		cnt += 1
	else:
		tmp = x
		flg.append(tmp)
		count.append(cnt)
		cnt = 1
count.append(cnt)

count += [0]*(2*K+1)
count = [0] + list(accumulate(count))

ans = 0

for i in range(len(flg)):
	if flg[i] == "1":
		ans = max(ans, count[i+2*K+1] - count[i])
	else:
		ans = max(ans, count[i+2*K] - count[i])

print(ans)



Measured memory_bytes: 100664
#include <iostream>
#include <queue>
#define INF 1000000000
#define NV 100000
using namespace std;
class edge
{
  public:
  int t;
  int d;
  edge *nextedge;
  edge(int,int);
};

edge::edge(int tt,int dd)
{
  t=tt;
  d=dd;
  nextedge=NULL;
}

class vertice
{
  public:
  int n;
  edge *firstedge;
  void create_edge(int,int);
};

void vertice::create_edge(int t,int d)
{
  edge *newedge=new edge(t,d);
  if(firstedge==NULL)
    firstedge=newedge;
  else
  {
    edge *tmp=firstedge;
    while(tmp->nextedge!=NULL)
    {
      tmp=tmp->nextedge;
    }
    tmp->nextedge=newedge;
  }
}

class source
{
  public:
  int n;
  int dis;
  friend bool operator<(source,source);
};

bool operator<(source a, source b)
{
  return a.dis>b.dis;
}

int main()
{
  int v,e,r;
  cin>>v>>e>>r;
  source weight[v];
  vertice vertices[v];
  for(int i=0;i<v;i++)
  {
    vertices[i].n=i;
    vertices[i].firstedge=NULL;
    weight[i].n=i;
    weight[i].dis=INF;
  }
  for(int i=0;i<e;i++)
  {
    int s,t,d;
    cin>>s>>t>>d;
    vertices[s].create_edge(t,d);
  }
/*
  for(int i=0;i<v;i++)
  {
    edge *p=vertices[i].firstedge;
    while(p!=NULL)
    {
      cout<<i<<' '<<p->t<<' '<<p->d<<endl;
      p=p->nextedge;
    }
  }
*/
  weight[r].dis=0;
  int current_vertex=r;
  priority_queue<source> queue;
  queue.push(weight[r]);
  while(queue.size()!=0)
  {
    source del=queue.top();
    queue.pop();
    current_vertex=del.n;
//    cout<<current_vertex<<endl;
    edge *p=vertices[current_vertex].firstedge;
    while(p!=NULL)
    {
      int vn=p->t;
      if(weight[vn].dis>weight[current_vertex].dis+p->d)
      {
        weight[vn].dis=weight[current_vertex].dis+p->d;
        queue.push(weight[vn]);
      }
//      cout<<vn<<' '<<weight[vn].dis<<' '<<weight[current_vertex].dis<<' '<<p->d<<endl;
      p=p->nextedge;
    }
  }
  for(int i=0;i<v;i++)
    if(weight[i].dis>=INF)
      cout<<"INF"<<endl;
    else
      cout<<weight[i].dis<<endl;
}

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


	



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

	bool flg=1;
	int v,counter=0;
	
	for(int i=0;flg;i++){
		flg =0;
		for(int j=n-1;i<j;j--){
			if(a[j-1]>a[j]){
				v=a[j-1];
				a[j-1]=a[j];
				a[j]=v;
				counter++;
				flg=1;
			}
			
		}
	}

	for(int i=0;i<n-1;i++){
		cout<<a[i]<<" ";
	}
	cout<<a[n-1]<<endl;
	cout<<counter<<endl;
	


	return 0;
}




Measured memory_bytes: 3080
def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    maximum, minimum = max(A), min(A)
    maxidx = A.index(maximum)
    minidx = A.index(minimum)
    ops = []

    for i in range(N):
        if abs(maximum) > abs(minimum):
            A[i] += maximum
            ops.append((maxidx, i))
        else:
            A[i] += minimum
            ops.append((minidx, i))
    
    #print(A)

    if abs(maximum) > abs(minimum):
        for i in range(0, N-1):
            ops.append((i, i+1))
            A[i+1] += A[i]
    else:
        for i in range(N-1, 0, -1):
            ops.append((i, i-1))
    
    #print(A)
    print(len(ops))
    [print(v[0]+1, v[1]+1) for v in ops]
    

if '__main__' == __name__:
    resolve()

Measured memory_bytes: 9216
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

H,W,K = II()
s = [str(input()) for _ in range(H)]
ans = [[0]*W for _ in range(H)]

count = 0
no_row = []
for i in range(H):
    p = []
    for j in range(W):
        if s[i][j]=='#':
            p.append(j)
    if len(p):
        count += 1
        for j in range(W):
            if s[i][j] == '#' and j!=p[0]:
                count += 1
            ans[i][j] = count
    else:
        no_row.append(i)

for i in no_row:
    for j in range(W):
        for k in range(i+1,H):
            if ans[k][j]:
                ans[i][j] = ans[k][j]
                break
        for k in range(i)[::-1]:
            if ans[k][j]:
                ans[i][j] = ans[k][j]
                break

for a in ans:
    print(*a)

Measured memory_bytes: 48220
#include <stdio.h>

int main(int argc, char const *argv[]) {
  char s[28]={};int length=0;
  scanf("%s",s);
  for (size_t i = 0; s[i]!='\0'; i++) {
    length++;
  }

  for (size_t i = 0; i < length; i++) {
    for (size_t j = i+1; j < length; j++) {
      if (s[i]==s[j]) {
        printf("no\n");
        return 0;
      }
    }
  }
  printf("yes\n");
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#include <time.h> 
#define ll long long int
#define F first
#define S second
#define pb push_back
#define sd(x) scanf("%d",&x)
#define sd2(x,y) scanf("%d%d",&x,&y);
#define sdl(x) scanf("%lld",&x)
#define sd2l(x,y) scanf("%lld%lld",&x,&y);
#define sz(x) (int)(x.size())
#define nax 1000010
#define inf 1001000100
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MOD 10000007 
#define mp make_pair
#define pc pair<char ,int>
#define pi pair<int ,int>
#define pii pair <pi,pi>
using namespace std;
int mat[20][20];
ll dp[65550];
int main(int argc, char const *argv[])
{
  //freopen("input.txt","r",stdin);
  //freopen("output.txt","w",stdout);
  int n;
  sd(n);
  for(int i = 0; i < n; i++)
  {
      for(int j = 0; j < n; j++)
        sd(mat[i][j]);
  }
  for(int mask = 1; mask < (1 << n); mask++)
  {
      if(!__builtin_popcount(mask) == 1)
        continue;
      ll cval = 0;
      for(int j = 0; j < n; j++)
      {
          if((mask >> j) & 1)
          {
            for(int k = j + 1; k < n ; k++)
            {
                if((mask >> k) & 1)
                  cval += mat[j][k];
            }
          }
      }
      dp[mask] = cval;
      for(int j = mask; j > 0; j = ((j - 1) &  mask))
      {
          if ((j & mask) == j)
              dp[mask] = max(dp[mask], dp[j] + dp[mask ^ j]);
      }
  }
  printf("%lld\n", dp[(1 << n) - 1]);
  return 0;
} 

Measured memory_bytes: 768
#include<stdio.h>

int n;
long int H[500001];

int parent(i){
  return i/2;
}

int left(i){
  return 2*i;
}

int right(i){
  return 2*i+1;
}

void maxHeapify(int i){
  int l,r,largest;
  long int x;
  l = left(i);
  r = right(i);

  if(l<=n && H[l]>H[i]) largest = l;
  else largest = i;
  if(r<=n && H[r]>H[largest]) largest = r;

  if(largest!=i){
    x = H[i];
    H[i] = H[largest];
    H[largest] = x;

    maxHeapify(largest);
  }
		      
}

void buildMaxHeap(){
  int i;
  for(i=n/2;i>=1;i--){
    maxHeapify(i);
  }
}
	       

int main(){

  int i;
  scanf("%d",&n);

  for(i=1;i<=n;i++){
    scanf("%ld",&H[i]);
  }

  buildMaxHeap();

  for(i=1;i<=n;i++){
    printf(" %ld",H[i]);
  }
  printf("\n");
  
  return 0;
}



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

int main() {
	long long n, a, b, ans, p, min, max;
	cin >> n >> a >> b;

	//ここでミスってる
	if ((n == 1 && a < b) || a > b) {
		ans = 0;
	}
	else {
		p = n-1;
		min = p*a + b;
		max = a + p*b;
		ans = max - min + 1;
	}

	cout << ans << endl;
}

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

int main() {
    int h, w;
    char s[52][52] = {};
    bool flg = true;
    
    cin >> h >> w;
    for ( int i = 0; i < h; i++ ) {
        for ( int j = 0; j < w; j++ ) {
            cin >> s[i+1][j+1];
        }
    }
    
    for ( int i = 1; i <= h; i++ ) {
        for ( int j = 1; j <= w; j++ ) {
            if ( s[i][j] == '#' ) {
                if ( s[i][j-1] == '.' && s[i][j+1] == '.' && s[i-1][j] == '.' && s[i+1][j] == '.' ) {
                    flg = 0;
                }
            }
        }
    }
    
    if ( flg ) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
    
    return (0);
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define rep(i,n) for (ll i = 0; i < n; ++i)
#define sz(x) int(x.size())
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())
#define FORV(i, v) for (auto i = v.begin(); i != v.end(); i++)
using namespace std;

using ll = long long;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const int INF = 1001001001;
const long long INFLL = LLONG_MAX / 3;
const double eps = (1e-9);

const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

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

  ll n, k;
  cin >> n >> k;
  mint ans;
  for (ll i = k; i <= n+1; i++) {
    ll mi = (i * (i-1)) / 2;
    ll ma = i * (n-i+1 + n) / 2;
    ll tmp = ma - mi + 1;
    ans += tmp;
  }

  cout << ans.x << endl;

  return 0;
}


Measured memory_bytes: 3640
#include<bits/stdc++.h>
#define MAX 1000001
using namespace std;
int main()
{
    bool hamming[MAX]={};
    for(int i=1;i<MAX;i*=2){
        for(int j=i;j<MAX;j*=3){
            for(int k=j;k<MAX;k*=5)hamming[k]=1;
        }
    }
    int m;
    while(cin>>m,m){
        int n,co=0;
        cin>>n;
        for(int i=m;i<=n;i++)if(hamming[i])co++;
        cout<<co<<endl;
    }
}

Measured memory_bytes: 2144
#include <iostream>
#include <algorithm>

using namespace std;

int main(int argc, char const *argv[])
{
    int A, B, C, X, Y;
    cin >> A >> B >> C >> X >> Y;
    int ans = 0;
    if (A + B < 2 * C)
    {
        ans = A * X + B * Y;
    }else
    {
        if (X < Y)
        {
            ans = 2 * C * X;
            ans += min(B * (Y - X), 2 * C * (Y - X));
        }else
        {
            ans = 2 * C * Y;
            ans += min(A * (X - Y), 2 * C * (X - Y));
        }
        
    }
    
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 256
N, T = map(int, input().split())
t = list(map(int, input().split()))

cnt = T
time = T

for i in range(1, N):
    if(t[i] <= time):
        cnt += (t[i]-time)+T
        time = t[i]+T
    else:
        time = t[i]+T
        cnt += T
print(cnt)

Measured memory_bytes: 25200
from itertools import *
n = int(input())
xy =[]
for i in range(n):
    tmp = int(input())
    testimony = []
    for j in range(tmp):
        testimony.append(list(map(int, input().split())))
    xy.append(testimony)
ans = 0
for p in product([0,1],repeat=n):

    flag = True
    if sum(p) <= ans:
        continue
    for i in range(n):
        if p[i] == 0:
            continue
        for test in xy[i]:
            if p[test[0]-1] != test[1]:
                flag = False
    if flag:
        ans = sum(p)

print(ans)


Measured memory_bytes: 47196
n = int(input())
a = [0] * n
b = [0] * n
for i in range(n):
    a[i],b[i] = map(int,input().split())
a.sort()
b.sort()
if n % 2 == 1:
    print(b[n//2] - a[n//2] + 1)
else:
    front = n//2
    back = (n-1)//2
    print((b[front] + b[back] - (a[front] + a[back]) + 1))


Measured memory_bytes: 75660
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int mo=1e9+7;
long long p[30];
char s[1000000];
int main()
{
	int n;
	scanf("%d",&n);
	scanf("%s",s+1);
	for (int i=1;i<=n;i++) p[s[i]-'a']++;
	long long ans=1;
	for (int i=0;i<=25;i++) ans=ans*(p[i]+1)%mo;
	ans=(ans-1+mo)%mo;
	printf("%lld\n",ans);
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<algorithm>
#include<utility>
#include<math.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const int INF = pow(10, 7);
int main(){
  string s;cin>>s;
  int n=(int)s.size();
  int ans=n, pos=1;
  string pre=string(1, s[0]);
  for(;pos<n;pos++){
    if(pre.size()==1){
      if(string(1, s[pos])==pre){
        if(pos==n-1){
          ans--;
        }else{
          ans--;
          pos++;
          pre = s.substr(n-2, 2);
        }
      }else{
        pre=s[pos];
      }
    }else{
      pre = s[pos];
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vi vector<ll>
#define pb push_back
#define ff first
#define ss second
#define inf 2e18
#define ull unsigned long long
#define pi acos(-1.0)
#define mod 1000000007
#define lop0(n) for(ll i=0;i<n;i++)
#define lopj(n) for(ll j=0;j<n;j++)
#define lop1(n) for(ll i=1;i<=n;i++)
#define all(v) v.begin(),v.end()
ll Set(ll N,ll pos){ return N=N | (1LL<<pos); }
ll reset(ll N,ll pos){ return N= N & ~(1LL<<pos); }
bool check(ll N,ll pos){ return (bool)(N & (1LL<<pos)); }
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

main()
{
   ll n,x,t;
   cin>>n>>x>>t;
   if(n%x) n+=x;
   ll ans=n/x;
   cout<<ans*t;
}



Measured memory_bytes: 3624
import java.io.*;
import java.util.*;


public class Main {

	private static Scanner sc;
	private static Printer pr;

	private static void solve() {
		char[] s = sc.next().toCharArray();
		long k = sc.nextLong();

		for (int i = 0, size = s.length; i < size && i < k; i++) {
			if (s[i] != '1') {
				pr.println(s[i]);
				return;
			}
		}
		
		pr.println(s[(int)k - 1]);
	}

	// ---------------------------------------------------
	public static void main(String[] args) {
		sc = new Scanner(INPUT == null ? System.in : new ByteArrayInputStream(INPUT.getBytes()));
		pr = new Printer(System.out);

		solve();

//		pr.close();
		pr.flush();
//		sc.close();
	}

	static String INPUT = null;

	private static class Printer extends PrintWriter {
		Printer(OutputStream out) {
			super(out);
		}
	}
}


Measured memory_bytes: 23124
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <map>
#include <functional>
#include <cmath>
#include <cstdint>
#include <mutex>
#include <thread>
#include <bitset>

using namespace std;

int main()
{
	int a[3];
	int i = 0;
	cin >> a[0] >> a[1] >> a[2];

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vec;
 
#define vecc vector<vector<ll>>
#define LM LLONG_MAX
 
#define int long long int
#define P pair<ll,ll>
 
#define ff first
#define ss second
 
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
 
#define N 200005
#define MOD (ll)1000000007

signed main()
{
      FAST;
      
      ll n,k;
      cin>>n>>k;
      
      ll dp[n+5];
      ll a[n+5];
      
      for(int i=1;i<=n;i++)         cin>>a[i];
      
      for(int i=0;i<=n;i++)         dp[i]=1e10;
            
      dp[1]=0;
      
      for(int i=2;i<=n;i++)
            for(int j=1;j<=k && (i-j)>0;j++)
                  dp[i]=min(dp[i],dp[i-j]+abs(a[i-j]-a[i]));
      
      cout<<dp[n]<<"\n";
      
}

Measured memory_bytes: 1792
#include <iostream>
#include <fstream>
#include <cassert>
#include <typeinfo>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#include <random>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<29;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

int x,y;
vb a(13,0);

int main(){
	a[4]=1;
	a[6]=1;
	a[9]=1;
	a[11]=1;
	cin>>x>>y;
	if(x==2||y==2||a[x]!=a[y]) cout<<"No"<<endl;
	else cout<<"Yes"<<endl;
}

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

using namespace std;

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

  int64_t dp[2][3];
  memset(dp, 0, sizeof(dp));
  for (int i = 0; i < N; i++) {
    int64_t v[3];
    cin >> v[0] >> v[1] >> v[2];
    dp[(i + 1) & 1][0] = max(dp[i & 1][1], dp[i & 1][2]) + v[0];
    dp[(i + 1) & 1][1] = max(dp[i & 1][2], dp[i & 1][0]) + v[1];
    dp[(i + 1) & 1][2] = max(dp[i & 1][0], dp[i & 1][1]) + v[2];
  }

  int64_t result = max({dp[N & 1][0], dp[N & 1][1], dp[N & 1][2]});
  printf("%ld\n", result);
  return 0;
}


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

int main() {
	int n,sum;
	while (cin >> n >> sum) {
		if (n == 0 && sum == 0) {
			break;
		}
		int count = 0;
		for (int i = 1;i != n-1;++i) {
			for (int j = i+1;j != n;++j) {
				for (int k = j+1;k != n+1;++k) {
					if (i + j + k == sum) {
						++count;
					}
				}
			}
		}
		cout << count << endl;
	}
}

Measured memory_bytes: 3060
#include<iostream>
#include<string>
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s,a;
    cin>>s>>a;
    reverse(s.begin(),s.end());
    {
        if(s==a)
        {
            cout<<"YES"<<endl;
        }
        else
        {
            cout<<"NO"<<endl;
        }
    }
}


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

const int RLEN=1<<18|1;
inline char nc() {
	static char ibuf[RLEN],*ib,*ob;
	(ib==ob) && (ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
	return (ib==ob) ? -1 : *ib++;
}
inline int rd() {
	char ch=nc(); int i=0,f=1;
	while(!isdigit(ch)) {if(ch=='-')f=-1; ch=nc();}
	while(isdigit(ch)) {i=(i<<1)+(i<<3)+ch-'0'; ch=nc();}
	return i*f;
}

const int N=4e2+5;

int n,m;
bitset <N> sta[N],ban;
int main() {
	n=rd(), m=rd();
	for(int i=1;i<=m;i++) {
		int x=rd(), y=rd();
		sta[x]|=sta[y];
		sta[y]|=sta[x];
		for(int j=1;j<=n;j++) {
			int tag1=sta[j].test(x), tag2=sta[j].test(y);
			if(tag1) sta[j].set(y);
			if(tag2) sta[j].set(x);
		}
		sta[x].set(y); sta[y].set(x);
	}
	for(int i=1;i<=n;i++) 
		if(sta[i][i]) ban[i]=1;
	int cnt=0;
	for(int i=1;i<=n;i++) if(!ban[i]) {
		bitset <N> tp=sta[i];
		for(int j=1;j<=n;j++) tp.flip(j);
		cnt+=tp.count();
		tp&=ban;
		cnt-=tp.count();
	} cout<<(cnt-(n-ban.count()))/2<<'\n';
}

Measured memory_bytes: 512
use std::collections::VecDeque;
fn main() {
    let n = read::<usize>();
    let aa = read_vec::<u32>();
    let mut b = VecDeque::new();

    for i in 0..n {
        if (i % 2 == 0 && n % 2 == 0) || (i % 2 != 0 && n % 2 != 0) {
            b.push_back(aa[i]);
        } else {
            b.push_front(aa[i]);
        }
    }
    println!(
        "{}",
        b.into_iter()
            .map(|i| i.to_string())
            .collect::<Vec<String>>()
            .join(" ")
    );
}

#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}
#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}
#[allow(dead_code)]
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
#[allow(dead_code)]
fn yn(result: bool) {
    if result {
        println!("Yes");
    } else {
        println!("No");
    }
}


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

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

using ll = long long;
constexpr ll INF = 10000000000;

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

using namespace std;

//fixed << setprecision(10)

/////////////////////////////////////////////////////////////////////////////////////////////////////////

int main() {
	double a, b, x; cin >> a >> b >> x;

	double ans = 0;

	if (a * a * b / 2 >= x) {
		double ok = 0;
		double ng = a;

		double ans_y = 0;

		rep(i, 100000) {
			double now = (ok + ng) / 2;

			if (a * b * now / 2 > x) {
				ng = now;
			}
			else {
				ok = now;
			}
		}

		ok /= b;

		double theta = atan(ok);

		double pai = acos(-1);

		ans = 90 - (theta * 180 / pai);
	}
	
	else {
		double ok = 0;
		double ng = b;

		//double ans_y = 0;

		rep(i, 100000) {
			double now = (ok + ng) / 2;

			if ((a * a * b) - (now * a * a / 2) > x) {
				ok = now;
			}
			else {
				ng = now;
			}
		}
		ok /= a;

		double theta = atan(ok);

		double pai = acos(-1);

		ans = theta * 180 / pai;
	}
	cout << fixed << setprecision(10) << ans << endl;
}


Measured memory_bytes: 512
package main

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

func main() {
	// scn := newScanner()
	// X := scn.nextLine()
	var X string
	fmt.Scan(&X)
	stack := make([]byte, 0)
	for i := 0; i < len(X); i++ {
		if X[i] == 'S' {
			stack = append(stack, X[i])
		} else if X[i] == 'T' && (len(stack) == 0 || stack[len(stack)-1] == 'T') {
			stack = append(stack, X[i])
		} else if X[i] == 'T' && stack[len(stack)-1] == 'S' {
			stack = stack[:len(stack)-1]
		}
	}
	fmt.Println(len(stack))
}

// func main() {
// 	scn := newScanner()
// 	X := scn.nextLine()
// 	stack := list.New()
// 	for i := 0; i < len(X); i++ {
// 		if X[i] == 'S' {
// 			stack.PushFront(X[i])
// 		} else if X[i] == 'T' && (stack.Len() == 0 || stack.Front().Value.(byte) == 'T') {
// 			stack.PushFront(X[i])
// 		} else if X[i] == 'T' && stack.Front().Value.(byte) == 'S' {
// 			_ = stack.Remove(stack.Front())
// 		}
// 	}
// 	fmt.Println(stack.Len())
// }
type scanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}

func newScanner() *scanner {
	rdr := bufio.NewReaderSize(os.Stdin, 10000)
	return &scanner{r: rdr}
}
func (s *scanner) next() string {
	s.pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	result := string(s.buf[start:s.p])
	s.p++
	return result
}
func (s *scanner) nextLine() string {
	s.pre()
	start := s.p
	s.p = len(s.buf)
	return string(s.buf[start:])
}
func (s *scanner) nextInt() int {
	v, _ := strconv.Atoi(s.next())
	return v
}
func (s *scanner) nextInt64() int64 {
	v, _ := strconv.ParseInt(s.next(), 10, 64)
	return v
}
func (s *scanner) pre() {
	if s.p >= len(s.buf) {
		s.readLine()
		s.p = 0
	}
}
func (s *scanner) readLine() {
	s.buf = make([]byte, 0)
	for {
		l, p, e := s.r.ReadLine()
		if e != nil {
			panic(e)
		}
		s.buf = append(s.buf, l...)
		if !p {
			break
		}
	}
}


Measured memory_bytes: 3072
fn read<T: std::str::FromStr>() -> T {
  let mut s = String::new();
  std::io::stdin().read_line(&mut s).ok();
  s.trim().parse().ok().unwrap()
}
 
fn main() {
  let s: String = read();
  if s.len() < 4 {
    println!("No");
    return
  };
  let ans = if &s[..4] == "YAKI" { "Yes" } else { "No" };
 
  println!("{}", ans);
}


Measured memory_bytes: 4352
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <string>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
using namespace std;
//________
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0; i<(n); ++i)
#define reps(i,f,n) for(int i=(f); i<=(n); ++i)
#define err(...) fprintf(stderr, __VA_ARGS__ )
#define show(x) cerr << #x << ':' << (x) << endl
#define outl(x) cout << (x) << '\n'
#define FAST() cin.tie(0), ios::sync_with_stdio(false)
typedef long long ll;
typedef pair<int,int> pii;
template<class A, class B>inline bool chmax(A &a, B b){return b>a ? a=b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, B b){return b<a ? a=b,1 : 0;}
inline bool inside(int y, int x, int H, int W){return(y>=0 && x>=0 && y<H && x<W);}
const int dx[] = {1, 0, -1, 0,  1, 1, -1, -1};
const int dy[] = {0, 1, 0, -1,  -1, 1, 1, -1};
#define Size 1000111
#define INF  0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define NIL -1
//________

int N, M, H, W;

signed main()
{
   FAST();
   int a,b;
   cin >> N >> a >> b;
   int p = abs(a-b);
   outl( p % 2 == 0 ? "Alice" : "Borys" );
}



Measured memory_bytes: 892
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<random>
#include<array>
#include<cassert>
using namespace std;
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define uniq(v) v.erase(unique(all(v)),v.end())

#define MOD 1000000007


int n, x;
int s[200];

long long dp[201][100001];

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

	cin >> n >> x;
	rep(i, n)cin >> s[i];
	sort(s, s + n);
	reverse(s, s + n);

	dp[0][x] = 1;


	rep(i, n) {
		rep(j, x + 1) {
			if (dp[i][j] == 0)continue;
			dp[i][j] %= MOD;

			dp[i + 1][j % s[i]] += dp[i][j];
			dp[i + 1][j] += dp[i][j] * (n - i - 1) % MOD;
		}
	}

	long long ans = 0;
	rep(i, x + 1) {
		ans += i * (dp[n][i] % MOD);
	}
	ans %= MOD;
	cout << ans << endl;


	return 0;
}

Measured memory_bytes: 154240
N = int(input())
L = list(map(int, input().split()))
L = sorted(L)

from bisect import bisect_left
def get_number_triangle(i, j, L):
    two_sum = L[i]+L[j]
    idx = bisect_left(L, two_sum)
    return idx - j - 1

ret = 0
for i in range(N):
    for j in range(i+1, N):
        ret += get_number_triangle(i, j, L)
print(ret)


Measured memory_bytes: 3188
n, k = list(map(int, input().split()))
p = list(map(int, input().split()))

def expect(p):
  return (p + 1) / 2

l = [0 for i in range(n+1)]
for i in range(1, n+1):
  l[i] = expect(p[i-1]) + l[i-1]

ans = 0
for i in range(k, n+1):
  ans = max(ans, l[i] - l[i-k])
print("{:.12f}".format(ans))

Measured memory_bytes: 25060
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;

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

       int t=1;
       //cin>>t;
       while(t--)
       {
               int a,b,h;
               cin>>a>>b>>h;
               cout<<((a+b)*h)/2;
       }
}


Measured memory_bytes: 3644
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <functional>
#include <map>
#include <queue>

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

using namespace std;
using ll = long long;
using P = pair<int, int>;
using TP = tuple<ll, ll, ll>;
ll MOD = 1e9+7;
//ll INF = 1LL<<40;
int INF = 1LL<<15;
int xv[4] = {-1, 1, 0, 0};
int yv[4] = {0, 0, -1, 1};


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N;
    cin >> N;
    vector<ll> H(N);
    REP(i, N){
        cin >> H[i];
    }
    
    for(int i = N-2; i >= 0; i--){
        //cout << i << ",";
        if(H[i] > H[i+1]){
            H[i]--;
            if(H[i] > H[i+1]){
                cout << "No" << endl;
                return 0;
            }
        }
        
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 1024
def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    ans = 1
    for i in range(N):
        if A[i]%2==1:
            pass
        else:
            ans *= 2
        
    print(3**N-ans)
if __name__ == '__main__':
    main()

Measured memory_bytes: 38256
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
  int N;
  cin >> N;
  vector<int> a(N);
  for (int i = 0; i < N; i++) {
    cin >> a[i];
  }
  sort(a.begin(), a.end());
 
  if (N == 1) {
    cout << 1 << endl;
    return 0;
  }
  
  int cnt = 1;
  int ans = 0;
  for (int i = 1; i < N; i++) {
    if (a[i] != a[i - 1]) {
    	ans += cnt % 2;
      	cnt = 1;
    } else {
    	cnt++;
   	}
  }
  ans += cnt % 2;
  cout << ans << endl;
  
  return 0;
}

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

const int mxN=15,mxM=1e3+10,mK=5e3+10,INF=1e8+10;
int n,m,k,x;
int total;
pair<int,int>v[mxM];
int dp[mxM][mK];

int solve(int index,int val){
    if(index==m && val!=total)return INF;
    if(val==total)return 0;
    if(dp[index][val]!=-1)return dp[index][val];
    return dp[index][val]=min(solve(index+1,val),solve(index+1,val|v[index].second)+v[index].first);
}
int32_t main(){
    memset(dp,-1,sizeof(dp));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    total=pow(2,n)-1;
    for(int i=0;i<m;i++){
        cin>>v[i].first>>k;
        v[i].second=0;
        for(int j=0;j<k;j++){
            cin>>x;
            v[i].second|=(1<<x-1);
        }

    }
    
    int resp=solve(0,0);
    (resp==INF)?cout<<-1:cout<<resp;

}


Measured memory_bytes: 20224
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
int main() {
  rep(i, 5) {
    ll x; cin>>x;
    if(x==0) cout << i+1;
  }
}

Measured memory_bytes: 3624
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
#include <stdio.h>
#include <cstring>
#include <iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <numeric>
#include <regex>
#include <locale>
#include <fstream>
#include <stdlib.h>
#include <cctype>

//#include <map>

using namespace std;

int main()
{
	double x1, y1, x2, y2;
	double x, y;
	double theta;
	double d;

	cin >> x1 >> y1 >> x2 >> y2;

	x = x2 - x1;
	y = y2 - y1;
	d = sqrt(x * x + y * y);

	cout << fixed << setprecision(6) << d << endl;
}

Measured memory_bytes: 3248
#include <algorithm>
#include <atcoder/all>
#include <cmath>
#include <complex>
#include <cstdio>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <sys/types.h>
#include <unistd.h>
#include <vector>

#pragma region macros
#define _overload(_1, _2, _3, name, ...) name
#define _rep(i, n) _range(i, 0, n)
#define _range(i, a, b) for (int i = int(a); i < int(b); ++i)
#define rep(...) _overload(__VA_ARGS__, _range, _rep, )(__VA_ARGS__)
#define _rrep(i, n) _rrange(i, n, 0)
#define _rrange(i, a, b) for (int i = int(a) - 1; i >= int(b); --i)
#define rrep(...) _overload(__VA_ARGS__, _rrange, _rrep, )(__VA_ARGS__)
#pragma endregion macros

using namespace std;
using namespace atcoder;

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

using ll    = long long;
using R     = long double;
const R EPS = 1e-9L;  // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R &r) {
    return (r > EPS) - (r < -EPS);
}
inline R sq(R x) {
    return sqrt(max(x, 0.0L));
}

const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

const pid_t pid = getpid();
// Problem Specific Parameter:

using mint = modint998244353;

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

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

    vector<int> coef(n);
    rep(i, n) coef[i] = max(i - k + 1, 0);

    mint ans = mint::raw(0);


    vector<int> idx(n);
    rep(i, n) idx[p[i]] = i;

    fenwick_tree<mint> small(n), large(n), num(n);

    const mint a = mint::raw(k - 1) / mint::raw(k);

    rep(i, n) {
        const int pos  = idx[i];
        const mint val = a.pow(coef[pos]);
        ans += val * small.sum(0, pos) / mint::raw(2);
        small.add(pos, val.inv());
    }

    rrep(i, n) {
        const int pos  = idx[i];
        const mint val = a.pow(coef[pos]);
        ans += num.sum(0, pos);
        ans -= val * large.sum(0, pos) / mint::raw(2);
        num.add(pos, mint::raw(1));
        large.add(pos, val.inv());
    }

    cout << ans.val() << endl;
    return 0;
}

Measured memory_bytes: 7636
#include "bits/stdc++.h"

using namespace std;
typedef long long ll;
#define rep(i,j,n) for (ll i = j; i < (n); i++)
#define CLR(mat) memset(mat, 0, sizeof(mat))
#define IN(a, b, x) (a<=x&&x<b)
#define out(ans) cout << ans << endl
typedef pair<ll,ll>P;
const ll mod=1e9+7;
const ll INF = 1e9;
ll n,m;
// ll a[100001000];
vector<ll>v;
ll ma;


// bool check(ll mid){
//   ll l=m;
//   ll p=ma;
//   while(l){

//     ll k=lower_bound(v.begin(),v.end(),p)-v.begin();
//     // cout<<k;
//     v[k]/=2;
//     p=v[k];
//     // cout<<k<<" "<<v[k]<<" "<<ma<<endl;
//     l--;
//   }
//   ll sum = accumulate(v.begin(),v.end(),0);
//   // out(sum);

//   if(sum>mid)return false;
//   else return true;
// }

int main(){

  cin>>n>>m;
  priority_queue<ll>pq;




  rep(i,0,n){
    ll a;cin>>a;
    // v.push_back(a);
    pq.push(a);
  }

  while(m){
    ll k=pq.top();
    // out(k);
    pq.pop();
    k/=2;
    pq.push(k);
    m--;
  }
  ll sum=0;
  while(!pq.empty()){
    sum+=pq.top();
    pq.pop();
  }

  out(sum);


  // sort(v.begin(),v.end(),greater<ll>());
  // rep(i,0,n)cout<<v[i]<<" ";
  // cout<<endl;
  // ma=v[0];
  // out(ma);

  // // ll ng=-1,ok=1e15;

  // // while(ok-ng>1){
  // //   ll mid=(ok+ng)/2;
  //   ll l=m;
  //   ll p=ma;
  //   while(l){


  //     // ll k=lower_bound(v.begin(),v.end(),p)-v.begin();
  //     // out(k);
  //     // cout<<k;
  //     v[k]/=2;
  //     p=v[k];
  //     // cout<<k<<" "<<v[k]<<" "<<ma<<endl;
  //     l--;
  //   }
  //   ll sum = accumulate(v.begin(),v.end(),0);
  //   out(sum);
  //   // if(sum>mid)ok=mid;
  //   // else ng=mid;
  //   // cout<<ng<<" "<<ok<<endl;
  // // out(sum);
  //   // out(ma);
  //   // if(check(mid))ok=mid;
  //   // else ng=mid;
  // // }
  // // out(ok);

  return 0;
}


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

public class Main {
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		
		System.out.println(Arrays.asList("a", "e", "i", "o", "u").contains(s) ? "vowel" : "consonant");
	}
}

Measured memory_bytes: 35712
#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

int main() {
  int h, n;
  cin >> h >> n;
  vector<int> vec(n);
  for (auto &v : vec)
    cin >> v;

  int vmax = accumulate(vec.begin(), vec.end(), 0);

  cout << ((h <= vmax)? "Yes" : "No") << endl;
}

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

string S;
int n, it;

int num() {
	int res = 0;
	while (it < n && isdigit(S[it])) {
		res = res * 10 + S[it] - '0';
		it++;
	}
	return res;
}

P parser(int t) {
	P res(0, '0');
	while (it < n && S[it] != ')') {
		if (isdigit(S[it])) {
			int nm = num();
			if (S[it] == '(') {
				it++;
				int tmp = it;
				auto p = parser(t);
				if (p.second != '0') {
					res.second = p.second;
					break;
				}
				else if (t < p.first * nm) {
					it = tmp;
					t %= p.first;
					res.second = parser(t).second;
					break;
				}
				t -= p.first * nm;
				res.first += p.first * nm;
				assert(S[it++] == ')');
			}
			else {
				if (t < nm) {
					res.second = S[it];
				}
				t -= nm;
				res.first += nm;
				it++;
			}
		}
		else {
			if (t == 0) {
				res.second = S[it];
			}
			t--;
			res.first++;
			it++;
		}
		if (t < 0) {
			break;
		}
	}
	return res;
}

int main()
{
	int i;
	while (cin >> S >> i, S != "0" || i != 0) {
		n = S.size();
		it = 0;
		cout << parser(i).second << endl;
	}
	return 0;
}

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

int main()
{
	ll n, k;
  cin >> n >> k;
  vector<ll> v;
  for (int i = 0;i < n;i++)
  {
   ll tmp;
    cin >> tmp;
    v.push_back(tmp);
  }
  sort(v.begin(), v.end());
  ll sum = 0;
  for (int i = 0; i < max(0LL, n-k);i++)
    sum+= v[i];
  cout << sum << endl;
}

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

#define ris   return *this
#define tmplt template<class T
#define dbgo  debug& operator<<
tmplt > struct rge { T b, e; };
tmplt > rge<T> range(T i, T j) { return rge<T>{i, j}; }
struct debug {
#ifdef LOCAL
~debug(){cerr<<endl;}
tmplt > dbgo(T x){cerr<<boolalpha<<x;ris;}
tmplt, class C > dbgo(pair<T, C> x){ris<<"("<<x.first<<", "<<x.second<<")";}
tmplt > dbgo(rge<T> x){*this<<"[";for(auto it=x.b;it!=x.e;it++){*this<<", "+2*(it==x.b)<<*it;}ris<<"]";}
tmplt > dbgo(vector<T> x){ris<<range(x.begin(),x.end());}
#else
tmplt > dbgo(const T&){ris;}
#endif
};
#define nav(...) << "[ " << #__VA_ARGS__ ": " << (__VA_ARGS__) << " ] "
using ll = long long;

#define forn(i, n) for(int i = 0; i < int(n); i++)
#define ford(i, n) for(int i = n-1; i >= 0; i--) 

template<typename T> 
void min_self(T& a, T b) { 
    a = min(a, b); 
}
template<typename T>
void max_self(T& a, T b) { 
    a = max(a, b); 
}


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

    string s;
    int k;
    cin >> s >> k;
    int n = s.length();
    
    set<string> best;
    auto add = [&](const string& t) {
        best.insert(t);
        while((int) best.size() > 5) {
            auto it = best.end();
            best.erase(--it);
        }
    };
    
    for(int i = 0; i < n; i++) {
        string t;
        for(int j = i; j < n; j++) {
            t.push_back(s[j]);
            add(t);
        }
    }
    while((int) best.size() > k) {
        auto it = best.end();
        best.erase(--it);
    }
    
    auto it = best.end();
    cout << *(--it) << endl;
}













// Don't worry, you're getting better

// Read statement carefully
// Solve on paper first!
// Make your infinity big enough
// Overflows (long long)

// Author: blondie


Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <numeric>
#include <iomanip>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 998244353; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;
struct INIT { 
  INIT(){cin.tie(0); ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
}}INIT;


signed main() {
  string s, t;
  cin >> s >> t;

  int N = s.size();
  bool ans = true;
  for(char c = 'a'; c <= 'z'; c++){
    vector<char> v;
    REP(i, N){
      if(s[i] != c) continue;
      v.emplace_back(t[i]);
    }
    if(v.size() == 0) continue;
    REP(i, v.size()){
      if(v[i] != v[0]) ans = false;
    }

    v = {};
    REP(i, N){
      if(t[i] != c) continue;
      v.emplace_back(s[i]);
    }
    if(v.size() == 0) continue;
    REP(i, v.size()){
      if(v[i] != v[0]) ans = false;
    }
  }

  ans? Yes: No;

  return 0;
}

Measured memory_bytes: 916