Posted on 2008-10-31 22:53
Hero 閱讀(132)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 // 1648 C++ Accepted 0.031 449 KB URAL
2
3 #include <stdio.h>
4 #include <stdlib.h>
5 #include <string.h>
6
7 //typedef long long llong ;
8 typedef __int64 llong ;
9
10 const int size = 20100 ;
11 struct NODE {
12 int num ;
13 int posi ;
14 };
15 struct NODE node[size] ;
16 struct NODE stack[size] ;
17 int top ;
18
19 int inn, ind ;
20 llong sum, total ;
21 llong mincost ;
22
23 void input()
24 {
25 sum = 0 ;
26 for( int i=1; i<=inn; i++ )
27 {
28 scanf( "%d", &node[i].num ) ;
29 sum += node[i].num ;
30 node[i].num -= ind ;
31 node[i].posi = i ;
32 }
33 }
34
35 void process()
36 {
37 top = -1 ; mincost = 0 ;
38 for( int i=inn; i>=1; i-- )
39 {
40 if( node[i].num > 0 )
41 {
42 stack[++top].num = node[i].num ;
43 stack[top].posi = node[i].posi ;
44 }
45 else if( node[i].num < 0 )
46 {
47 int temp = node[i].num ;
48 while( top >= 0 && temp < 0 )
49 {
50 int curnum = stack[top].num ;
51 int curposi = stack[top].posi ;
52 top -- ;
53 if( curnum+temp > 0 )
54 {
55 curnum = curnum + temp ;
56 mincost += abs(temp) * abs(curposi-node[i].posi) ;
57 temp = 0 ;
58 stack[++top].num = curnum ; stack[top].posi = curposi ;
59 }
60 else if( curnum + temp < 0 )
61 {
62 temp = curnum + temp ;
63 mincost += abs(curnum) * abs(curposi-node[i].posi) ;
64 }
65 else
66 {
67 temp = curnum + temp ;
68 mincost += abs(curnum) * abs(curposi-node[i].posi) ;
69 }
70 }
71 }
72 }//for
73
74 total = 0 ;
75 for( int i=0; i<=top; i++ ) total += stack[i].num ;
76 printf( "%I64d %I64d\n", sum-total, mincost ) ;
77 }
78
79 int main()
80 {
81 while( scanf( "%d %d", &inn, &ind ) != EOF )
82 {
83 input() ;
84
85 process() ;
86
87 //output() ;
88 }
89
90 return 0 ;
91 }